You are given a permutation $\{a_1, a_2, \dots, a_n\}$ of $\{1, 2, \dots, n\}$, and you need to transform it into $\{1, 2, \dots, n\}$.

You can perform operations in two stages. In the first stage, you can perform any number of operations, where each operation consists of choosing two adjacent elements and swapping them. In the second stage, you can perform any number of operations, where each operation consists of changing the value of an element at any position. In the second stage, you can modify elements arbitrarily; even if the sequence is no longer a permutation during the intermediate steps, it is still valid.

You need to minimize the total number of operations across both stages and provide a valid sequence of operations that achieves this minimum. For simplicity, you only need to output the operations for the first stage. The SPJ (Special Judge) will automatically calculate the optimal operations for the second stage and compare the total number of operations with the optimal total.

Input

The first line contains a positive integer $n$. The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$.

Output

The first line outputs the number of operations $u$ in the first stage. The second line outputs $u$ space-separated positive integers $p_1, p_2, \dots, p_u$ ($1 \le p_i < n$), representing the sequence of swaps: $(a_{p_1}, a_{p_1+1}), (a_{p_2}, a_{p_2+1}), \dots, (a_{p_u}, a_{p_u+1})$.

Examples

Input 1

4
4 3 2 1

Output 1

1
2

Note

In the first stage, the two middle elements are swapped. In the second stage, the first and fourth elements are modified, requiring a total of 3 operations. It can be proven that this is optimal.

Subtasks

Subtask 1 (10pts): $n \le 5$. Subtask 2 (10pts): $n \le 9$. Subtask 3 (10pts): $n \le 50$. Subtask 4 (20pts): $n \le 500$. Subtask 5 (10pts): $n \le 2000$. Subtask 6 (20pts): $n \le 10^5$. Subtask 7 (20pts): $n \le 2 \times 10^5$.