국회의원 선거

다솜이는 사람이 누구에게 투표할지 미리 알 수 있는 기계를 가지고 있다. 한 사람이 이미 투표할 후보를 정했다면, 실제 선거에서도 반드시 그 후보에게 투표한다.

현재 형택구에는 국회의원 후보가 N명 있고, 다솜이는 기호 1번 후보이다. 다솜이는 기계를 이용해 마을 주민들의 투표 의향을 모두 확인했다.

다솜이는 자신에게 투표하지 않으려는 사람을 돈으로 매수해 자신의 표로 바꾸려고 한다. 매수된 사람은 반드시 다솜이에게 투표한다. 어떤 후보가 당선되려면 그 후보의 득표수가 다른 모든 후보의 득표수보다 엄격하게 많아야 한다.

예를 들어 기호 1번이 5표, 기호 2번이 7표, 기호 3번이 7표라면, 다솜이는 2번 후보에게 투표하려던 사람 1명과 3번 후보에게 투표하려던 사람 1명을 매수해 당선될 수 있다.

다솜이가 당선되기 위해 매수해야 하는 사람 수의 최솟값을 구하라.

첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 N개의 줄에는 기호 1번 후보부터 기호 N번 후보까지, 각 후보에게 투표하려는 사람 수가 순서대로 주어진다.

N은 50 이하의 자연수이고, 각 득표수는 100 이하의 자연수이다.

다솜이가 매수해야 하는 사람 수의 최솟값을 한 줄에 출력한다.