描述

房间中现有\( n \)枚灯泡，编号从\( 1 \)~\( n \)，自左向右排成一排。

最初0时刻时，所有的灯都是关着的。

在\( k \)时刻，我们打开编号为\( k \)的灯。

这里的灯可变成蓝白两色。

灯的颜色要想变成蓝色，就必须同时满足下面两个条件：

·灯处于打开状态。

·排在它左侧的所有灯也都处于打开状态。

请返回能够让所有开着的灯都变成蓝色的时刻数目 。

格式

输入

输入有两行。

第一行，一个整数n

第二行，n个整数表示当前时刻打开灯的编号

输出

一个整数，表示有多少个时刻所有亮着的灯都变成蓝色

样例

输入

5
3 1 2 5 4

输出

2

样例解释

0表示灭的灯，1表示白色的灯，2表示蓝色的灯
时刻1：0 0 1 0 0
时刻2：2 0 1 0 0
时刻3：2 2 2 0 0
时刻4：2 2 2 0 1
时刻5：2 2 2 2 2
亮着的时刻为：时刻3，时刻5

范围

\( 1<n<5*10^5+1\)
\( 0<k<n+1 \)