题目描述

有 $N$ 个人，这 $N$ 个人编号为 $1 \sim N$，第 $h$ 个人的身高为 $h$。

有 $N$ 个台阶，这 $N$ 个台阶从低到高编号为 $1 \sim N$，第 $i$ 级台阶比第 $i+1$ 个台阶低 $2$ 个单位高度。每个台阶上只能站一个人，第 $H_i$ 个人站在第 $i$ 个台阶上。

你可以进行无数次如下操作：

• 选择 $i \in [1,N-1]$，交换第 $i$ 个台阶上的人和第 $i+1$ 个台阶上的人。

假设第 $i$ 个台阶上站的人的高度为 $a_i$，你要满足：

• 对于任意 $i \in [1,N-1]$，都有 $a_i <a_{i+1}+2$。

求最少的操作次数。

输入格式

第一行一个整数 $N$ 代表人数。

第二行 $N$ 个整数 $H_i$ 代表第 $H_i$ 个人站在第 $i$ 个台阶上。

输出格式

一行一个整数代表最少的操作次数。

5
3 5 2 4 1

3

5
3 2 1 5 4

0

9
6 1 3 4 9 5 7 8 2

9

提示

样例 1 解释

设 $h_i$ 为第 $i$ 个台阶上站的人的身高：

• 交换第 $2$ 个人和第 $3$ 个人，$h_i=\{3,2,5,4,1\}$。
• 交换第 $4$ 个人和第 $5$ 个人，$h_i=\{3,2,5,1,4\}$。
• 交换第 $3$ 个人和第 $4$ 个人，$h_i=\{3,2,1,5,4\}$。

$3$ 步刚好满足要求。

样例 2 解释

已经满足要求，不需要进行任何操作。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（5 pts）：$N \le 9$。
• Subtask 2（7 pts）：$N \le 20$。
• Subtask 3（32 pts）：$N \le 200$。
• Subtask 4（20 pts）：$N \le 800$。
• Subtask 5（36 pts）：无特殊限制。

对于 $100\%$ 的数据，$3 \le N \le 5000$，$1 \le H_i \le N$，$H_i$ 互不相等。

说明

翻译自 The 20th Japanese Olympiad in Informatics Final Round C 集合写真的英文翻译 Group Photo。