체인

희원이는 다락방에서 N개의 체인을 찾았다. 각 체인은 여러 개의 고리가 일렬로 연결된 형태이며, 한 고리는 최대 두 개의 이웃한 고리와 연결될 수 있다.

각 고리는 열었다가 다시 닫을 수 있다. 고리를 열면 체인을 나누거나, 두 체인을 이어 하나의 더 긴 체인으로 만들 수 있다. 희원이는 가능한 한 적은 수의 고리만 열고 닫아서 모든 체인을 하나의 긴 체인으로 연결하려고 한다.

예를 들어, 고리 하나로만 이루어진 체인이 세 개 있다면, 그중 하나의 고리를 열어 나머지 두 체인을 연결한 뒤 다시 닫으면 된다.

체인의 개수와 각 체인의 길이가 주어질 때, 모든 체인을 하나로 묶기 위해 열고 닫아야 하는 고리 수의 최솟값을 구하라.

첫 번째 줄에 체인의 개수 N이 주어진다.

두 번째 줄에 각 체인의 길이를 나타내는 N개의 정수 L_i가 주어진다.

2 <= N <= 500000

1 <= L_i <= 1000000

모든 체인을 하나의 긴 체인으로 연결하기 위해 열고 닫아야 하는 고리 수의 최솟값을 출력한다.