The big Noel is a guy full of habits. This year he put all of his reindeer in a row and decided to select the most of them, following a few rules.

• Reindeer can not be changed in order, i.e. a reindeer that is in position i in the original row should appear before the reindeer j in the chosen list, where i < j.
• Reindeer of two adjacent positions in the final sequence must differ exactly by 1 (right-left=1) unit in their heights.

If that was not enough, Noel realized that this sequence had few reindeer. So she decided to include a new reindeer in the original row. Taking into account that this new reindeer can be inserted in any position and he will always choose a reindeer with the best possible height.

After making the task a little difficult, Noel ended up getting confused and is asking for your help to find out how many reindeer can be selected taking into account the rules imposed.

Input

The first line of the entry contains an integer N (1 ≤ N ≤ 10⁵) corresponding to the number of reindeer. In the second line contains N integers X_i (1 ≤ X_i ≤ 10⁶) which represents the height of the ith reindeer.

Output

Print as many reindeer as Noel can select.

Example

Input:
4
1 1 2 2
Output:
3