[Solution] Breaking the Wall solution codeforces

Breaking the Wall solution codeforces – 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.

[Solution] Breaking the Wall solution codeforces

The wall consists of 𝑛n sections, aligned in a row. The 𝑖i-th section initially has durability 𝑎𝑖ai. 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 𝑥x, then the durability of the section 𝑥x decreases by 22, and the durability of the sections 𝑥1x−1 and 𝑥+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!

[Solution] Breaking the Wall solution codeforces

The first line contains one integer 𝑛n (2𝑛21052≤n≤2⋅105) — the number of sections.

The second line contains the sequence of integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1061≤ai≤106), where 𝑎𝑖ai is the initial durability of the 𝑖i-th section.

Output

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

Examples
input

Copy
5
20 10 30 10 20

output

Copy
10


[Solution] Breaking the Wall solution codeforces

input

Copy
3
1 8 1

output

Copy
1

input

Copy
6
7 6 6 8 5 8

output

Copy
4

input

Copy
6
14 3 8 10 15 4

output

Copy
4

input

Copy
4
1 100 100 1

output

Copy
2

input

Copy
3
40 10 10

output

Copy
7


Breaking the Wall solution codeforces

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.