← 返回题目列表

AtCoder · agc014_f

F. 奇怪的排序

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

分数: 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