Emuskald 沉迷于 Codeforces,并且不断刷新主页,不错过“最近操作”列表中的任何变化。他喜欢阅读线程对话,其中每个线程包含多条消息。
最近的操作显示了按线程中最新消息的时间排序的 n 个不同线程的列表。当在线程中发布新消息时,该线程会跳转到列表顶部。不同线程的两条消息不会同时发布。
Emuskald 刚刚读完所有打开的帖子,并刷新主页以获取更多消息来满足他的瘾。他注意到列表中没有出现新线程,并且列表中的第 i 个位置有一个线程在刷新之前位于第 ai 个位置。他不想浪费任何时间阅读旧消息,因此他只想打开包含新消息的线程。
帮助 Emuskald 找出肯定有新消息的线程数。如果不存在满足这两个条件的线程更新(发布消息)序列,则线程 x 肯定有新消息:
1. 线程 x 未更新(没有新消息);
2. 列表顺序 1, 2, ..., n 更改为 a1, a2, ..., an。
输入
输入的第一行包含一个整数 n,即线程数 (1 ≤ n ≤ 105)。下一行包含 n 个空格分隔的整数 a1, a2, ..., an 的列表,其中 ai (1 ≤ ai ≤ n) 是新列表中第 i 个线程的旧位置。保证所有的ai都是不同的。
输出
输出一个整数——肯定包含新消息的线程数。
示例
输入 #1
5 5 2 1 3 4
输出 #1
2
输入 #2
3 1 2 3
输出 #2
0
输入 #3
4 4 3 2 1
输出 #3
3
注意
在第一个测试用例中,线程 2 和 5 放置在线程 1 之前,因此这些线程必须包含新消息。如果只有线程 2 和 5 有新消息,则线程 1、3 和 4 可能不包含新消息。
在第二个测试用例中,可能根本没有新消息,因为线程顺序没有改变。
在第三个测试用例中,只有线程 1 不能包含新消息。