分数: 600 点
问题陈述
Snuke 得到了一个长度为整数的序列 N 来自他母亲的生日礼物。的 i-th (1 ≦ i ≦ N) 序列的元素是 a_i。这些元素是成对不同的。 他正在按升序对这个序列进行排序。 凭借神通,他可以对序列进行任意顺序的以下两种操作:
- 操作 1:选择 2 连续元素,然后反转这些元素的顺序。
- 操作 2:选择 3 连续元素,然后反转这些元素的顺序。
Snuke 喜欢行动 2,但不是操作 1。求最小操作次数 他必须执行 1 才能按升序对序列进行排序。
约束
- 1 ≦ N ≦ 10^5
- 0 ≦ A_i ≦ 10^9
- If i ≠ j,那么 A_i ≠ A_j.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 : A_N
输出
打印最小次数操作 Snuke 必须表演的 1 。
示例输入 1
4 2 4 3 1
示例输出 1
1
给定的序列可以排序如下:
- 首先,反转最后三个元素的顺序。现在的顺序是: 2,1,3,4.
- 然后,反转前两个元素的顺序。现在的顺序是: 1,2,3,4.
在此操作序列中,操作 1 执行一次。无法对操作次数较少的序列进行排序 1,因此答案是 1.
示例输入 2
5 10 8 5 3 2
示例输出 2
0