Maximizing Tower Value

PinkRabbit has received a tower of n blocks from his npy. The tower is built by stacking n blocks where each block is marked with an integer. The tower is represented as \(\{a_1, a_2, \dots, a_n\}\), where \(a_i\) is the number on the i-th block from the bottom.

The value of a tower with m blocks is defined as

[ \text{value} = \sum_{i=1}^{m} \bigl[ a_i = i \bigr], ]

where \(\bigl[ a_i = i \bigr]\) is \(1\) if \(a_i = i\) and \(0\) otherwise.

You are allowed to remove any number of blocks (possibly none) from the tower. When some blocks are removed, the remaining blocks fall down and form a new tower (i.e. their order is preserved and they are reindexed from \(1\)).

Your task is to choose a subset of blocks (in their original order) to form a new tower such that its value is maximized.

Example

Consider the tower \(\{1, 1, 2, 4, 5\}\). If no blocks are removed, the positions and values are:

• Position 1: 1 (match)
• Position 2: 1 (no match, since 1 \(\neq\) 2)
• Position 3: 2 (no match, since 2 \(\neq\) 3)
• Position 4: 4 (match)
• Position 5: 5 (match)

Thus, the value is \(1 + 0 + 0 + 1 + 1 = 3\). It can be verified that no deletion can produce a tower with a higher value. Therefore, the answer is 3.

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\) representing the number of blocks.
• The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\), where \(a_i\) is the number on the i-th block (from bottom to top).

outputFormat

Print a single integer — the maximum possible value of the tower after removing an arbitrary set of blocks.

sample

5
1 1 2 4 5

3