如果在内存条上施加食人魔诅咒会发生什么？事实证明，它可以在夜间高效地循环移动任意数据序列。

请找出将长度为 $n$ 的排列 $v$ 排序所需的最小代价（以及一组有效的移动序列）。排列的所有元素下标从 $1$ 到 $n$。

唯一允许的移动方式是：选取某个位置 $x$ 上的元素，将其插入到另一个位置 $y$，并将中间的所有元素向后或向前平移一位。此类移动的代价为 $y$。

形式化地讲，一次移动选取位置 $x$ 上的元素 $t$，使位置 $x$ 变为“空闲”。然后，我们将 $v$ 中的剩余元素平移，使得“空闲”位置变为 $y$。最后，我们将 $t$ 放入位置 $y$。

例如，如果我们有一个排列 $[4, 3, 2, 1]$，一些可能的移动如下：

• $x = 2, y = 4$，得到的排列为 $[4, 2, 1, 3]$，移动代价为 $4$。
• $x = 2, y = 1$，得到的排列为 $[3, 4, 2, 1]$，移动代价为 $1$。

输入格式

第一行包含一个整数 $n$ —— 排列的长度。 第二行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$ —— 排列的数值。

数据范围

$1 \le n \le 3 \cdot 10^5$ $1 \le v_i \le n$ 对于所有 $1 \le i < j \le n$，满足 $v_i \neq v_j$。

输出格式

第一行输出两个数字 $min\_cost$ 和 $len\_moves$ —— 排序排列所需的最小代价以及所建议的移动序列长度。 接下来的 $len\_moves$ 行，每行包含两个整数 $x_k, y_k$，表示第 $k$ 次操作应将位置 $x_k$ 上的元素移动到位置 $y_k$（$1 \le k \le len\_moves, 1 \le x_k, y_k \le n$）。

如果存在多种可能的移动序列，输出其中任意一种即可。注意，你不需要最小化移动次数，只需最小化总代价。题目保证一定存在将排列排序的移动序列。

样例

样例输入 1

4
1 2 4 3

样例输出 1

3 1
4 3

样例输入 2

5
2 4 1 3 5

样例输出 2

3 2
4 2
4 1

样例输入 3

3
1 2 3

样例输出 3

0 0

说明

• 对于第一个样例，唯一的移动实际上交换了位置 $3$ 和 $4$ 上的元素。
• 对于第二个样例，第一次移动后得到的排列为 $[2, 3, 4, 1, 5]$。
• 对于第三个样例，排列已经有序，因此最优代价为零，无需进行任何移动。