테트리스 리마스터드

Mila는 테트리스를 좋아한다. 오늘 그녀는 테트리스와 비슷한 새 게임을 알게 되었다. 이 게임에는 아래쪽과 너비가 $n$인 무한한 직사각형 필드가 있고, $1 \times 1$ 크기의 칸으로 나뉘어 있다. 실제 테트리스와 달리 이 게임에서는 높이 $1$, 너비 $x$인 가로 조각, 즉 $x$개의 칸으로 이루어진 $1 \times x$ 크기의 조각을 사용한다. 다음 조각이 떨어지기 전에 플레이어는 그 크기 $x$를 $1$ 이상 $n$ 이하의 임의의 정수로 정할 수 있다. 조각은 회전할 수 없지만 왼쪽이나 오른쪽으로 움직일 수 있다. 조각은 아래에 있는 점유된 칸이나 필드의 바닥에 닿을 때까지 떨어진다.

Mila는 조각 아래에 빈 칸을 남기는 것을 싫어한다. 그녀의 목표는 필드의 아래쪽 행들을 채워서 모든 점유된 칸이 너비 $n$인 직사각형을 이루도록 하는 것이다.

필드의 상태 $a_1, a_2, \ldots, a_n$이 주어진다. 여기서 $a_i$는 필드의 $i$번째 열에 있는 점유된 칸의 수이다. 주어진 필드에는 점유된 칸 아래에 빈 칸이 없다. 예를 들어 수열 $a$가 $3, 2, 4, 2, 2, 4$이면 필드는 다음과 같다.

Mila가 필드의 아래쪽 행들을 채워 너비 $n$인 직사각형을 만들기 위해 두어야 하는 조각의 최소 개수를 구하라.

첫째 줄에 정수 $n$이 주어진다. $n$은 필드의 너비이다 ($1 \le n \le 2 \cdot 10^5$).

둘째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 주어진다. $a_i$는 필드의 각 열에 있는 점유된 칸의 수이다 ($0 \le a_i \le 10^9$).

적어도 하나의 $a_i$는 $0$보다 크다.

Mila가 너비 $n$인 직사각형을 만들기 위해 필요한 조각의 최소 개수를 나타내는 정수 하나를 출력한다.

예제에서 Mila는 다음 네 개의 조각을 사용할 수 있다.