codeforces#P1674E. Breaking the Wall

    ID: 32914 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchbrute forceconstructive algorithmsgreedymath

Breaking the Wall

Description

Monocarp plays "Rage of Empires II: Definitive Edition" — a strategic computer game. Right now he's planning to attack his opponent in the game, but Monocarp's forces cannot enter the opponent's territory since the opponent has built a wall.

The wall consists of nn sections, aligned in a row. The ii-th section initially has durability aia_i. If durability of some section becomes 00 or less, this section is considered broken.

To attack the opponent, Monocarp needs to break at least two sections of the wall (any two sections: possibly adjacent, possibly not). To do this, he plans to use an onager — a special siege weapon. The onager can be used to shoot any section of the wall; the shot deals 22 damage to the target section and 11 damage to adjacent sections. In other words, if the onager shoots at the section xx, then the durability of the section xx decreases by 22, and the durability of the sections x1x - 1 and x+1x + 1 (if they exist) decreases by 11 each.

Monocarp can shoot at any sections any number of times, he can even shoot at broken sections.

Monocarp wants to calculate the minimum number of onager shots needed to break at least two sections. Help him!

The first line contains one integer nn (2n21052 \le n \le 2 \cdot 10^5) — the number of sections.

The second line contains the sequence of integers a1,a2,,ana_1, a_2, \dots, a_n (1ai1061 \le a_i \le 10^6), where aia_i is the initial durability of the ii-th section.

Print one integer — the minimum number of onager shots needed to break at least two sections of the wall.

Input

The first line contains one integer nn (2n21052 \le n \le 2 \cdot 10^5) — the number of sections.

The second line contains the sequence of integers a1,a2,,ana_1, a_2, \dots, a_n (1ai1061 \le a_i \le 10^6), where aia_i is the initial durability of the ii-th section.

Output

Print one integer — the minimum number of onager shots needed to break at least two sections of the wall.

Samples

输入数据 1

5
20 10 30 10 20

输出数据 1

10

输入数据 2

3
1 8 1

输出数据 2

1

输入数据 3

6
7 6 6 8 5 8

输出数据 3

4

输入数据 4

6
14 3 8 10 15 4

输出数据 4

4

输入数据 5

4
1 100 100 1

输出数据 5

2

输入数据 6

3
40 10 10

输出数据 6

7

Note

In the first example, it is possible to break the 22-nd and the 44-th section in 1010 shots, for example, by shooting the third section 1010 times. After that, the durabilities become [20,0,10,0,20][20, 0, 10, 0, 20]. Another way of doing it is firing 55 shots at the 22-nd section, and another 55 shots at the 44-th section. After that, the durabilities become [15,0,20,0,15][15, 0, 20, 0, 15].

In the second example, it is enough to shoot the 22-nd section once. Then the 11-st and the 33-rd section will be broken.

In the third example, it is enough to shoot the 22-nd section twice (then the durabilities become [5,2,4,8,5,8][5, 2, 4, 8, 5, 8]), and then shoot the 33-rd section twice (then the durabilities become [5,0,0,6,5,8][5, 0, 0, 6, 5, 8]). So, four shots are enough to break the 22-nd and the 33-rd section.