시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 135 54 50 46.296%

문제

희원이는 그의 다락방에서 N개의 체인을 찾았다. 각각의 체인은 몇개의 고리로 연결되어 있는데, 각각의 고리는 최대 두 개의 인접한 고리를 가질 수 있다. 각각의 고리는 열려 있거나 닫혀 있다. 그래서, 체인은 분리되거나 더 강한 체인이 되기 위해 함께 연결될 수 있다. 희원이는 가능한 적은 체인이 열리고 닫히게 하여, 모든 체인을 하나의 큰 체인으로 연결하려고 한다.

예를 들어, 희원이가 각각 하나의 고리를 생성할 수 있는 오직 세 개의 체인을 갖고 있을 때, 그 중 하나를 열어서 나머지 두개를 연결하고 닫을 수 있다

체인의 개수와 각각의 체인의 길이가 주어지면, 하나의 긴 체인으로 모든 체인을 묶기 위해 희원이가 열고 닫아야할 최소한의 고리 수를 찾아라.

입력

첫번째 줄에는 체인의 개수를 나타내는 양의 정수 N (2 ≤ N ≤ 500000)이 주어진다. 두번째 줄에는 각각의 체인의 길이를 나타내는 N개의 양의 정수 Li(1 ≤ Li ≤ 1000000)가 주어진다.

출력

첫째 줄에 필요한 고리의 최소 개수를 출력한다.

예제 입력 1

5
4 3 5 7 9

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjI3ODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjYjRcdWM3NzgiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YjI5NCBcdWFkZjhcdWM3NTggXHViMmU0XHViNzdkXHViYzI5XHVjNWQwXHVjMTFjIE5cdWFjMWNcdWM3NTggXHVjY2I0XHVjNzc4XHVjNzQ0IFx1Y2MzZVx1YzU1OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2NiNFx1Yzc3OFx1Yzc0MCBcdWJhODdcdWFjMWNcdWM3NTggXHVhY2UwXHViOWFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFjZTBcdWI5YWNcdWIyOTQgXHVjZDVjXHViMzAwIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjNzc4XHVjODExXHVkNTVjIFx1YWNlMFx1YjlhY1x1Yjk3YyBcdWFjMDBcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWNlMFx1YjlhY1x1YjI5NCBcdWM1ZjRcdWI4MjQgXHVjNzg4XHVhYzcwXHViMDk4IFx1YjJlYlx1ZDYwMCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYywgXHVjY2I0XHVjNzc4XHVjNzQwIFx1YmQ4NFx1YjlhY1x1YjQxOFx1YWM3MFx1YjA5OCBcdWIzNTQgXHVhYzE1XHVkNTVjIFx1Y2NiNFx1Yzc3OFx1Yzc3NCBcdWI0MThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU2OFx1YWVkOCBcdWM1ZjBcdWFjYjBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNzZjXHVjNmQwXHVjNzc0XHViMjk0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM4MDFcdWM3NDAgXHVjY2I0XHVjNzc4XHVjNzc0IFx1YzVmNFx1YjlhY1x1YWNlMCBcdWIyZWJcdWQ3ODhcdWFjOGMgXHVkNTU4XHVjNWVjLCBcdWJhYThcdWI0ZTAgXHVjY2I0XHVjNzc4XHVjNzQ0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWQwNzAgXHVjY2I0XHVjNzc4XHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YWMwMCBcdWFjMDFcdWFjMDEgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWNlMFx1YjlhY1x1Yjk3YyBcdWMwZGRcdWMxMzFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2MjRcdWM5YzEgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWNjYjRcdWM3NzhcdWM3NDQgXHVhYzE2XHVhY2UwIFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YWRmOCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YzVmNFx1YzViNFx1YzExYyBcdWIwOThcdWJhMzhcdWM5YzAgXHViNDUwXHVhYzFjXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YWNlMCBcdWIyZWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNDxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NoYWluLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDE4NnB4OyBoZWlnaHQ6IDEzN3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWNjYjRcdWM3NzhcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNjYjRcdWM3NzhcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWUzNCBcdWNjYjRcdWM3NzhcdWM3M2NcdWI4NWMgXHViYWE4XHViNGUwIFx1Y2NiNFx1Yzc3OFx1Yzc0NCBcdWJiMzZcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YWMwMCBcdWM1ZjRcdWFjZTAgXHViMmViXHVjNTQ0XHVjNTdjXHVkNTYwIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWFjZTBcdWI5YWMgXHVjMjE4XHViOTdjIFx1Y2MzZVx1YzU0NFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjY2I0XHVjNzc4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBOICgyICZsZTsgTiAmbGU7IDUwMDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNjYjRcdWM3NzhcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggTGkoMSAmbGU7IExpICZsZTsgMTAwMDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWFjZTBcdWI5YWNcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjc4NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkxBTkNJIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMgZm91bmQgTiBjaGFpbnMgaW4gaGlzIGF0dGljLiBFYWNoIGNoYWluIGNvbnNpc3RzIG9mIHNvbWUgbnVtYmVyIG9mIGxpbmtzLCB3aGVyZSBlYWNoIGxpbmsgaGFzIGF0IG1vc3QgdHdvIGFkamFjZW50IGxpbmtzLiBFYWNoIGxpbmsgY2FuIGJlIG9wZW5lZCBvciBjbG9zZWQsIHNvIGl0IGlzIHBvc3NpYmxlIHRvIHNlcGFyYXRlIGNoYWlucyBvciBjb25uZWN0IHRoZW0gaW50byBhIGxvbmdlciBjaGFpbi4gTWlya28gd291bGQgbGlrZSB0byBjb25uZWN0IGFsbCBjaGFpbnMgaW50byBvbmUgaHVnZSBjaGFpbiwgd2hpbGUgb3BlbmluZyBhbmQgY2xvc2luZyBhcyBmZXcgbGlua3MgYXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiBNaXJrbyBoYXMgb25seSB0aHJlZSBjaGFpbnMsIGVhY2ggY29uc2lzdGluZyBvZiBvbmx5IG9uZSBsaW5rLCBoZSBjYW4gb3BlbiBvbmUgb2YgdGhlbSwgdXNlIGl0IHRvIGNvbm5lY3QgdGhlIHJlbWFpbmluZyB0d28gYW5kIGNsb3NlIGl0OjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NoYWluLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzN3B4OyBvcGFjaXR5OjAuOTsgd2lkdGg6MTg2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIG51bWJlciBvZiBjaGFpbnMgYW5kIHRoZSBsZW5ndGggb2YgZWFjaCBjaGFpbiwgZmluZCB0aGUgbWluaW11bSBudW1iZXIgb2YgbGlua3MgdGhhdCBNaXJrbyBoYXMgdG8gb3BlbiBhbmQgY2xvc2UgaW4gb3JkZXIgdG8gYmluZCB0aGVtIGFsbCBpbiBkYXJrbmVzcyBvbmUgbG9uZyBjaGFpbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgNTAwIDAwMCksIHRoZSBudW1iZXIgb2YgY2hhaW5zLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBwb3NpdGl2ZSBpbnRlZ2VycyBMPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IEw8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgMDAwKSwgdGhlIGxlbmd0aHMgb2YgaW5kaXZpZHVhbCBjaGFpbnM8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBtaW5pbXVtIG51bWJlciBvZiBsaW5rcy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d