2024sccpc题面

我们知道逆序对的定义：对于一个长度为 $n$ 的排列 $a_1,a_2,\dots,a_n$，如果有 $i<j$ 且 $a_i>a_j$，那么称 $a_i,a_j$ 为一组逆序对。一个长度为 $n$ 的排列满足 $1$ 到 $n$ 恰好各出现一次。

求逆序对的个数什么的对你来说应该不是什么难题了。现在给你一个长度为 $n$ 的排列 $a_1,a_2,\dots,a_n$，对于每一对满足 $i<j$ 且 $a_i>a_j$ 的逆序对，在大小为 $n \times n$ 的网格图上把第 $i$ 行第 $a_j$ 列的格子染色。请问最终的网格图上染色的连通块有几个？连通是指，如果两个被染色的格子有一条公共边，那么我们认为这两个格子是连通的。

Input

第一行一个整数 $n$（$1 \le n \le 3 \times 10^5$），表示排列的长度。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示一个长度为 $n$ 的排列。

Output

输出一个整数，表示最终的网格图上的连通块的个数。

Examples

9
5 9 1 8 2 6 4 7 3

5

2
1 2

0