시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 38 15 13 39.394%

문제

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

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

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

입력

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

출력

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

예제 입력

5
4 3 5 7 9

예제 출력

3

힌트