Building Blocks

Time limit1sMemory limit128 MB

Summary

Remove blocks from a tower so the most remaining blocks sit at an altitude equal to their printed number.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy, Sorting
Solved: No attempts yet

Problem

Little Jessica received a set of building blocks for her birthday. The blocks are all cubes of the same size, and each block has a positive integer written on it. Delighted with the gift, she immediately stacked every block into one tall tower.

Her mother explained the game: reshape the tower so that as many blocks as possible sit in their proper place. A block with the number $i$ written on it is in its proper place when it rests at altitude $i$ . The bottom block is at altitude $1$ , the block above it at altitude $2$ , and so on.

Jessica may carefully remove some of the blocks. Whenever a block is removed, every block above it slides down by one, and the altitudes are renumbered from the bottom. She wants to remove blocks so that the number of blocks left in their proper place is as large as possible.

Given the tower Jessica first built, determine the largest number of blocks that can end up in their proper place.

Input

The first line contains a single integer $n$ ( $1 \le n \le 100000$ ), the initial height of the tower. The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 1000000$ ), separated by single spaces, where $a_i$ is the number written on the block at altitude $i$ in the initial tower, listed from the lowest block to the highest.

Output

Print a single integer: the maximum number of blocks that can be in their proper place after Jessica removes some blocks.

Hint

Examples4

Example 1
Input
```
5
1 1 2 5 4
```
Expected output
```
3
```
Example 2
Input
```
1
1
```
Expected output
```
1
```
Example 3
Input
```
1
5
```
Expected output
```
0
```
Example 4
Input
```
5
1 2 3 4 5
```
Expected output
```
5
```