시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 32 MB 6 2 (33%) 2
문제
밀코는 그의 다락방에서 N개의 사슬들을 발견했다. 각 사슬은 몇개의 연결을 가지고있었는데, 인접한 연결은 최대 두개까지이다. 각 연결은 열거나 닫을 수 있어서, 이것은 사슬들을 분리하거나 연결해 더 긴사슬을 만드는 것이 가능하게 해준다. 밀코는 모든 사슬들을 연결해서 하나의 거대 사슬을 만들고자 하는데, 가능한 가장 적은 연결들을 열고 닫고싶다. 예를들어, 만약 밀코가 세개의 사슬이 있고 각각이 단 하나의 연결만 갖고있다면, 하나를 열어서 두개를 연결하고 닫아서 하나로 합칠 수 있다. ![그림1](/download_file/8de6fa4d91d63e05c085c8c60b7e1b4dfd3b6ebaa8b10517bdea4e44eb73e110/chains.png/?show=true) 사슬들의 갯수와 각 사슬들의 길이가 주어지면, 하나의 긴 (어둠의) 체인을 만들기 위해 필요한 최소횟수의 연결을 열고 닫는 횟수를 구하여라.
입력
첫번째 줄에는 자연수 N (2<=N<=500 000), 사슬의 갯수이다. 두번째 줄에는 N개의 자연수 Li (1<=Li<=1 000 000), 각 사슬들의 길이가 주어진다.
출력
첫번째 줄에 단하나의 줄로 요구한 최소 횟수의 연결수를 출력한다.
힌트
입력예제1 ``` 2 3 3 ``` 출력예제1 ``` 1 ``` 입력예제2 ``` 3 1 1 1 ``` 출력예제2 ``` 1 ``` 입력예제3 ``` 5 4 3 5 7 9 ``` 출력예제3 ``` 3 ``` 첫번째 예제의 설명 : 밀코는 첫번째 사슬의 마지막 연결을 열고, 두번째 사슬의 첫번째 연결을 넣은뒤 닫는다. 세번째 예제의 설명: 가장 좋은 방법은 길이 3짜리 사슬을 모두 끊어서, 나머지 사슬들을 연결하는데 사용하는 것이다.