Description

Given a sequence $A_i$ of length $N$, you can perform the following operation:

Choose a position $i$ and change $A_i$ to $A_i \oplus A_{i+1}$ or $A_i \oplus A_{i-1}$.

You want to know how many operations are needed to make $A_i$ become:

• $S=1$, a strictly increasing sequence, i.e. $A_i < A_{i+1}$.
• $S=2$, a non-strictly increasing sequence, i.e. $A_i \le A_{i+1}$.

Input Format

The first line contains two integers $N, S$, representing the length of the sequence and the test point type.
The second line contains $N$ integers $A_i$, representing the sequence.

Output Format

The first line contains an integer $K$, representing the number of operations. You do not need to minimize $K$; you only need to satisfy $0 \le K \le 4 \times 10^4$.
The next $K$ lines each contain two integers $i, j$, meaning to change $A_i$ to $A_i \oplus A_j$, where $j=i+1$ or $j=i-1$.

5 1
3 2 8 4 1

3
1 2
4 3
5 4

5 2
4 4 2 0 1

3
3 2
4 3
5 4

Hint

Explanation for Sample 1

$$[3, 2, 8, 4, 1] \to [\mathbf 1, 2, 8, 4, 1] \to [1, 2, 8, \mathbf{12}, 1] \to [1, 2, 8, 12, \mathbf{ 13}]$$

Explanation for Sample 2

$$[4, 4, 2, 0, 1] \to [4, 4, \mathbf6, 0, 1] \to [4, 4, 6, \mathbf6, 1] \to [4, 4, 6, 6, \mathbf7]$$

Constraints

This problem uses bundled testdata.

• Subtask 1 (25 pts): $2 \le N \le 150$, $S=1$, and all $A_i$ are distinct.
• Subtask 2 (35 pts): $2 \le N \le 200$, $S=1$, and all $A_i$ are distinct.
• Subtask 3 (40 pts): $2 \le N \le 1000$, $S=2$.

For $100\%$ of the testdata:

• $1 \le S \le 2$.
• $2 \le N \le 1000$.
• $0 \le A_i < 2^{20}$.

This problem uses Special Judge.

Note

Translated from eJOI 2020 Day2 A XOR Sort。

Translated by ChatGPT 5