← 返回题目列表

AtCoder · agc003_c

C. 气泡排序!

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

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