分数: 2400 点
问题陈述
高桥喜欢排序。
他有一个排列 (p_1,p_2,...,p_N) 中的整数 1 通过 N。现在,他将重复以下操作,直到排列变为 (1,2,...,N):
- 首先,我们将定义 高 和 低 元素的排列如下。的 i如果排列中的最大元素为高,则排列中的第一个元素为高。 1-st 和 i第一个元素(含)是 i-第一个元素本身,否则 i第一个元素低。
- 然后,让 a_1,a_2,...,a_k 是高位元素的值,并且 b_1,b_2,...,b_{N-k} 是当前排列中低位元素的值, 按照它们出现的顺序.
- 最后,将排列重新排列为 (b_1,b_2,...,b_{N-k},a_1,a_2,...,a_k).
在排列排序之前需要多少次操作?
约束
- 1 ≤ N ≤ 2×10^5
- (p_1,p_2,...,p_N) 是以下整数的排列 1 通过 N.
输入
输入由标准输入按以下格式给出:
N p_1 p_2 ... p_N
输出
打印排列排序之前所需的操作数。
示例输入 1
5 3 5 1 2 4
示例输出 1
3
初始排列是 (3,5,1,2,4),每个操作都会将其更改如下:
- 在第一次操作中, 1-st 和 2-nd 元素含量高,且 3-rd, 4-th 和 5-th 较低。排列变为: (1,2,4,3,5).
- 在第二次操作中, 1-st, 2-nd, 3-rd 和 5第个元素很高,并且 4-th 较低。排列变为: (3,1,2,4,5).
- 在第三次操作中, 1-st, 4-th 和 5第个元素很高,并且 2-nd 和 3-rd 和 5-th 较低。排列变为: (1,2,3,4,5).
示例输入 2
5 5 4 3 2 1
示例输出 2
4
示例输入 3
10 2 10 5 7 3 6 4 9 8 1
示例输出 3
6