Pool

Interview

Time limit6sMemory limit1024 MB

Summary

Given N distance readings from the shore, find the minimum number of pool lengths Bajtek must have swum to produce them.

Level: Medium5 of 10
Topics: Greedy, Implementation
Solved: No attempts yet

Problem

Bajtek finally bought a waterproof smartwatch. He went straight to the pool to check that it works. The watch is rather strange. At various moments it recorded how far Bajtek was from the start of the pool, that is, from the shore where he started. Bajtek read the sequence of recorded distances, but he does not understand how to interpret it. He wants to know the minimum number of pool lengths he could have swum.

You may assume that Bajtek turned around only after reaching the far end of the pool, and that he started and finished at the shore, even if the watch did not record this. Bajtek may sometimes stop to rest, not necessarily at the edge of the pool.

Input

The first line contains one natural number $N$ , $1 \le N \le 1\,000\,000$ , the number of readings on the watch. The second and last line contains $N$ integers $P_1, P_2, \ldots, P_N$ , $0 \le P_i \le 10^9$ , the successive distances from a fixed shore of the pool. At least one of the numbers $P_1, P_2, \ldots, P_N$ is not zero.

Output

Print one integer, the minimum number of pool lengths Bajtek swam.

Examples3

Example 1
Input
```
7
3 7 11 11 6 2 4
```
Expected output
```
3
```
Example 2
Input
```
9
1 2 3 4 5 4 3 2 1
```
Expected output
```
2
```
Example 3
Input
```
6
28 28 28 28 28 28
```
Expected output
```
1
```