문제
찬식이는 로봇 제작 키트를 이용해서 로봇을 만들다가
체인이 필요해서 키트를 뒤졌더니 체인이 붙은 채로 N조각이 발견되었다.
각 체인은 Li개의 고리가 일렬로 연결된 채로 발견되었다.
찬식이는 N조각의 체인들을 아래와 같은 방법으로 연결해서 하나의 '일렬로 연결된' 체인을 만들 것이다.
1. 고리 하나를 연다. 2. 그 고리를 다른 고리에 끼운다. 3. 고리를 다시 닫는다.
찬식이가 최소 몇 개의 고리를 열어야 N개의 체인을 모두 연결시킬 수 있을지 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 체인의 수 N이 주어진다. (2 ≤ N ≤ 500,000) 두 번째 줄에는 각 체인을 이루고 있는 고리의 수 Li가 주어진다. (1 ≤ Li ≤ 1,000,000)
출력
찬식이가 N개의 체인을 모두 연결시키기 위해서 열어야 하는 고리의 수의 최솟값을 출력한다.
예제1
입력
2
33
출력
1
예제2
입력
3
111
출력
1
예제3
입력
5
43579
출력
3
출처
COCI 2012/2013 Contest 2 LANCI