← 返回题目列表

Codeforces · 270/B

B. 多线程

中文机器翻译题面 查看原题

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 不能包含新消息。