23855번 - Tetris Remastered 서브태스크다국어

문제

Mila likes to play Tetris. Today she learnt about a new game that is similar to Tetris. The new game has an infinite rectangular field with the bottom and width equal to $n,ドル divided into cells of size 1ドル \times 1$. Unlike real Tetris in this game horizontal pieces with height 1ドル$ and width $x$ consisting of $x$ cells --- of size 1ドル \times x,ドル are used. Before the next piece starts to fall, a player can choose it's size $x$ as any integer between 1ドル$ and $n,ドル inclusive. Pieces can't be rotated, but they can be moved left or right. A piece falls until it reaches an occupied cell under it or the bottom of the field.

Mile doesn't like to leave empty cells under the pieces. Her goal is to fill lower rows of the field in the way that all occupied cells form a rectangle of width $n$.

You are given a field state: $a_1, a_2, \ldots, a_n,ドル where $a_i$ --- the number of occupied cells in the $i$-th column of the field. In the given field no empty cell is under the occupied one. For example, if sequence $a$ is 3,ドル 2, 4, 2, 2, 4,ドル the field looks like this:

Find the minimum number of pieces Mila needs to play to occupy the lower rows of the field forming a rectangle of width $n$.

입력

The first line contains a single integer $n$ --- the width of the field (1ドル \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ --- the number of occupied cells in each column of the field (0ドル \le a_i \le 10^9$).

At least on of the $a_i$ is strictly greater than 0ドル$.

출력

Print a single integer: the minimum number of pieces Mila will need to build a rectangle of width $n$.

제한

서브태스크

힌트

In the example Mile can use the following four pieces: