CF270B Multithreading

Emuskald 痴迷于 Codeforces，总是不断刷新主页，以便不会错过“最新动态”列表中的任何变化。他喜欢阅读每个由多条消息组成的主题帖的会话。 “最新动态”显示了 $n$ 个不同的主题帖，按主题帖中最新消息的时间顺序排列。当某个主题帖有新消息被发布时，该主题会跳到列表顶部。不会出现不同主题帖同时有消息发布的情况。 Emuskald 刚刚读完所有已打开的主题帖，刷新主页以获取更多消息。他注意到没有新的主题帖出现在列表中，并且刷新后第 $i$ 个位置上的主题帖在刷新前位于第 $a_i$ 个位置。他不想浪费时间阅读旧消息，因此只想打开包含新消息的主题帖。 请你帮助 Emuskald 计算出，哪些主题帖一定含有新消息，也就是**在任何可能的消息更新顺序中都无法避免含有新消息**的主题帖数量。形式化地说，如果无法构造出一组消息发送顺序，使得以下两个条件同时成立： 1. 主题帖 $x$ 没有收到新消息（不被更新）； 2. 列表顺序由 $1,2,\dots,n$ 变为 $a_1,a_2,\dots,a_n$； 那么主题帖 $x$ 一定有新消息。请计算这样的主题帖数量。

输入的第一行包含一个整数 $n$，表示主题帖数量（$1 \leq n \leq 10^5$）。下一行包含 $n$ 个用空格分隔的整数 $a_1,a_2,\dots,a_n$，其中 $a_i$（$1 \leq a_i \leq n$）表示刷新前位于第 $a_i$ 个位置的主题帖现在在第 $i$ 个位置上。保证所有 $a_i$ 互不相同。

输出一个整数，表示一定含有新消息的主题帖数量。

在第一个样例中，主题帖 2 和 5 被放到了主题帖 1 前面，所以这些主题帖必须含有新消息。主题帖 1、3 和 4 可能不含新消息，如果仅有主题帖 2 和 5 有新消息时可以达成结果。 在第二个样例中，列表顺序未改变，可能完全没有新消息。 在第三个样例中，只有主题帖 1 可能没有新消息。 由 ChatGPT 5 翻译