1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Poman Numbers
Contest: Technocup 2021 - Elimination Round 3
Difficulty rating: 2300
Tags: bitmasks, greedy, math, strings

You've got a string $$$S$$$ consisting of $$$n$$$ lowercase English letters from your friend. It turned out that this is a number written in poman numerals. The poman numeral system is long forgotten. All that's left is the algorithm to transform number from poman numerals to the numeral system familiar to us. Characters of $$$S$$$ are numbered from $$$1$$$ to $$$n$$$ from left to right. Let's denote the value of $$$S$$$ as $$$f(S)$$$, it is defined as follows:

- If $$$|S| > 1$$$, an arbitrary integer $$$m$$$ ($$$1 \le m < |S|$$$) is chosen, and it is defined that $$$f(S) = -f(S[1, m]) + f(S[m + 1, |S|])$$$, where $$$S[l, r]$$$ denotes the substring of $$$S$$$ from the $$$l$$$-th to the $$$r$$$-th position, inclusively.
- Otherwise $$$S = c$$$, where $$$c$$$ is some English letter. Then $$$f(S) = 2^{pos(c)}$$$, where $$$pos(c)$$$ is the position of letter $$$c$$$ in the alphabet ($$$pos($$$a$$$) = 0$$$, $$$pos($$$z$$$) = 25$$$).

Note that $$$m$$$ is chosen independently on each step.

Your friend thinks it is possible to get $$$f(S) = T$$$ by choosing the right $$$m$$$ on every step. Is he right?

Input format:
The first line contains two integers $$$n$$$ and $$$T$$$ ($$$2 \leq n \leq 10^5$$$, $$$-10^{15} \leq T \leq 10^{15}$$$).

The second line contains a string $$$S$$$ consisting of $$$n$$$ lowercase English letters.

Output format:
Print "Yes" if it is possible to get the desired value. Otherwise, print "No".

You can print each letter in any case (upper or lower).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the second example, you cannot get $$$-7$$$. But you can get $$$1$$$, for example, as follows:

1. First choose $$$m = 1$$$, then $$$f($$$abc$$$) = -f($$$a$$$) + f($$$bc$$$)$$$
2. $$$f($$$a$$$) = 2^0 = 1$$$
3. $$$f($$$bc$$$) = -f($$$b$$$) + f($$$c$$$) = -2^1 + 2^2 = 2$$$
4. In the end $$$f($$$abc$$$) = -1 + 2 = 1$$$

Example input:
2 -1
ba

Example output:
Yes

Example input:
3 -7
abc

Example output:
No

Editorial:
First, note that the last digit will always be taken with a plus sign, and the one before the last — with a minus sign. It turns out that all other digits may be taken with any sign. Let's prove it.
Suppose we want to get the mask $$$---++--++---+$$$. All minuses on the left can be obtained by simply splitting one character at a time. We are left with the $$$++--++---+$$$ mask, split it as follows: $$$(++--++-)(--+)$$$. That is, we left in the left part only one minus from the last segment of consecutive minuses. Change the signs in the left part: $$$(--++--+)(--+)$$$. We reduced it to a smaller problem. Doing this, we will end up with masks of the form $$$+$$$.
Now the problem is reduced to whether we can get the number $$$X$$$ using the first $$$n - 2$$$ letters. Since the weights of the items are powers of two, we can choose them greedily.
Bonus. Can you construct an answer in linear time (i.e. output a binary tree)?
No Game No Life
Contest: Technocup 2021 - Elimination Round 3
Difficulty rating: 2700
Tags: bitmasks, games, math, matrices

Let's consider the following game of Alice and Bob on a directed acyclic graph. Each vertex may contain an arbitrary number of chips. Alice and Bob make turns alternating. Alice goes first. In one turn player can move exactly one chip along any edge outgoing from the vertex that contains this chip to the end of this edge. The one who cannot make a turn loses. Both players play optimally.

Consider the following process that takes place every second on a given graph with $$$n$$$ vertices:

1. An integer $$$v$$$ is chosen equiprobably from $$$[1, n + 1]$$$.
2. If $$$v \leq n$$$, we add a chip to the $$$v$$$-th vertex and go back to step 1.
3. If $$$v = n + 1$$$, Alice and Bob play the game with the current arrangement of chips and the winner is determined. After that, the process is terminated.

Find the probability that Alice will win the game. It can be shown that the answer can be represented as $$$\frac{P}{Q}$$$, where $$$P$$$ and $$$Q$$$ are coprime integers and $$$Q \not\equiv 0 \pmod{998\,244\,353}$$$. Print the value of $$$P \cdot Q^{-1} \bmod 998\,244\,353$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ — the number of vertices and edges of the graph ($$$1 \leq n \leq 10^5$$$, $$$0 \leq m \leq 10^5$$$).

The following $$$m$$$ lines contain edges description. The $$$i$$$-th of them contains two integers $$$u_i$$$ and $$$v_i$$$ — the beginning and the end vertices of the $$$i$$$-th edge ($$$1 \leq u_i, v_i \leq n$$$). It's guaranteed that the graph is acyclic.

Output format:
Output a single integer — the probability of Alice victory modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
1 0

Example output:
0

Example input:
2 1
1 2

Example output:
332748118

Editorial:
The winner of the game is determined by xor of Grundy values for all chips' vertices. Notice that every Grundy value $$$\leq\sqrt m$$$ so xor doesn't exceed 512. Let $$$P_v$$$ be a probability of Alice's victory if the current xor is $$$v$$$.
$$$P_v = \sum P_{to}\cdot prob(v \rightarrow to) + [v\neq 0] \cdot\frac{1}{n + 1}$$$
In the second term, we got $$$n + 1$$$ and the process ended. It is clear that $$$prob(v \rightarrow to) = \frac{cnt[v \oplus to]}{n + 1}$$$, where $$$cnt[x]$$$ is the number of vertices with the Grundy value equal to $$$x$$$. Now we have a system of 512 linear equations with variables $$$P_v$$$. We can solve it using the Gauss method. The answer is in $$$P_0$$$. The proof that Gauss won't break along the way is left to the reader as an exercise.
There is also a solution using the Hadamard transform.
Distinct Buttons
Contest: Pinely Round 3 (Div. 1 + Div. 2)
Difficulty rating: 800
Tags: implementation, math

You are located at the point $$$(0, 0)$$$ of an infinite Cartesian plane. You have a controller with $$$4$$$ buttons which can perform one of the following operations:

- $$$\texttt{U}$$$: move from $$$(x, y)$$$ to $$$(x, y+1)$$$;
- $$$\texttt{R}$$$: move from $$$(x, y)$$$ to $$$(x+1, y)$$$;
- $$$\texttt{D}$$$: move from $$$(x, y)$$$ to $$$(x, y-1)$$$;
- $$$\texttt{L}$$$: move from $$$(x, y)$$$ to $$$(x-1, y)$$$.

Unfortunately, the controller is broken. If you press all the $$$4$$$ buttons (in any order), the controller stops working. It means that, during the whole trip, you can only press at most $$$3$$$ distinct buttons (any number of times, in any order).

There are $$$n$$$ special points in the plane, with integer coordinates $$$(x_i, y_i)$$$.

Can you visit all the special points (in any order) without breaking the controller?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of special points.

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$, $$$y_i$$$ ($$$-100 \leq x_i, y_i \leq 100$$$), which represent the special point $$$(x_i, y_i)$$$.

Note that there are no constraints on the sum of $$$n$$$ over all test cases.

Output format:
For each test case, output "YES" (without quotes), if you can reach all the special points without breaking the controller, and "NO" (without quotes) otherwise.

You may output each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can move as follows:

- you start from $$$(0, 0)$$$;
- you visit the special point $$$(x_2, y_2) = (0, 0)$$$;
- you press $$$\texttt{R}$$$, and you move from $$$(0, 0)$$$ to $$$(1, 0)$$$;
- you press $$$\texttt{D}$$$, and you move from $$$(1, 0)$$$ to $$$(1, -1)$$$;
- you visit the special point $$$(x_1, y_1) = (1, -1)$$$;
- you visit the special point $$$(x_3, y_3) = (1, -1)$$$.

Therefore, you can visit all the special points using only the buttons $$$\texttt{R}$$$, $$$\texttt{D}$$$, so the controller does not break.

Note that the special points may coincide.

In the second test case, you can show that you can visit all the special points using only the buttons $$$\texttt{U}$$$, $$$\texttt{D}$$$, $$$\texttt{L}$$$.

In the third test case, you can show that you must press all the buttons ($$$\texttt{U}$$$, $$$\texttt{R}$$$, $$$\texttt{D}$$$, $$$\texttt{L}$$$) to visit all the points, so the controller would break.

Example input:
6
3
1 -1
0 0
1 -1
4
-3 -2
-3 -1
-3 0
-3 1
4
1 1
-1 -1
1 -1
-1 1
6
-4 14
-9 -13
-14 5
14 15
-8 -4
19 9
6
82 64
39 91
3 46
87 83
74 21
7 25
1
100 -100

Example output:
YES
YES
NO
NO
YES
YES

Editorial:
Make Almost Equal With Mod
Contest: Pinely Round 3 (Div. 1 + Div. 2)
Difficulty rating: 1200
Tags: bitmasks, constructive algorithms, math, number theory

You are given an array $$$a_1, a_2, \dots, a_n$$$ of distinct positive integers. You have to do the following operation exactly once:

- choose a positive integer $$$k$$$;
- for each $$$i$$$ from $$$1$$$ to $$$n$$$, replace $$$a_i$$$ with $$$a_i \text{ mod } k^\dagger$$$.

Find a value of $$$k$$$ such that $$$1 \leq k \leq 10^{18}$$$ and the array $$$a_1, a_2, \dots, a_n$$$ contains exactly $$$2$$$ distinct values at the end of the operation. It can be shown that, under the constraints of the problem, at least one such $$$k$$$ always exists. If there are multiple solutions, you can print any of them.

$$$^\dagger$$$ $$$a \text{ mod } b$$$ denotes the remainder after dividing $$$a$$$ by $$$b$$$. For example:

- $$$7 \text{ mod } 3=1$$$ since $$$7 = 3 \cdot 2 + 1$$$
- $$$15 \text{ mod } 4=3$$$ since $$$15 = 4 \cdot 3 + 3$$$
- $$$21 \text{ mod } 1=0$$$ since $$$21 = 21 \cdot 1 + 0$$$

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{17}$$$) — the initial state of the array. It is guaranteed that all the $$$a_i$$$ are distinct.

Note that there are no constraints on the sum of $$$n$$$ over all test cases.

Output format:
For each test case, output a single integer: a value of $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$) such that the array $$$a_1, a_2, \dots, a_n$$$ contains exactly $$$2$$$ distinct values at the end of the operation.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can choose $$$k = 7$$$. The array becomes $$$[8 \text{ mod } 7, 15 \text{ mod } 7, 22 \text{ mod } 7, 30 \text{ mod } 7] = [1, 1, 1, 2]$$$, which contains exactly $$$2$$$ distinct values ($$$\{1, 2\}$$$).

In the second test case, you can choose $$$k = 30$$$. The array becomes $$$[0, 0, 8, 0, 8]$$$, which contains exactly $$$2$$$ distinct values ($$$\{0, 8\}$$$). Note that choosing $$$k = 10$$$ would also be a valid solution.

In the last test case, you can choose $$$k = 10^{18}$$$. The array becomes $$$[2, 1]$$$, which contains exactly $$$2$$$ distinct values ($$$\{1, 2\}$$$). Note that choosing $$$k = 10^{18} + 1$$$ would not be valid, because $$$1 \leq k \leq 10^{18}$$$ must be true.

Example input:
5
4
8 15 22 30
5
60 90 98 120 308
6
328 769 541 986 215 734
5
1000 2000 7000 11000 16000
2
2 1

Example output:
7
30
3
5000
1000000000000000000

Editorial:
Small Permutation Problem (Easy Version)
Contest: Pinely Round 3 (Div. 1 + Div. 2)
Difficulty rating: 2200
Tags: brute force, combinatorics, dp, math

In the easy version, the $$$a_i$$$ are in the range $$$[0, n]$$$; in the hard version, the $$$a_i$$$ are in the range $$$[-1, n]$$$ and the definition of good permutation is slightly different. You can make hacks only if all versions of the problem are solved.

You are given an integer $$$n$$$ and an array $$$a_1, a_2 \dots, a_n$$$ of integers in the range $$$[0, n]$$$.

A permutation $$$p_1, p_2, \dots, p_n$$$ of $$$[1, 2, \dots, n]$$$ is good if, for each $$$i$$$, the following condition is true:

- the number of values $$$\leq i$$$ in $$$[p_1, p_2, \dots, p_i]$$$ is exactly $$$a_i$$$.

Count the good permutations of $$$[1, 2, \dots, n]$$$, modulo $$$998\,244\,353$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$), which describe the conditions for a good permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single line containing the number of good permutations, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the only good permutation is $$$[1, 2, 3, 4, 5]$$$.

In the second test case, there are $$$4$$$ good permutations: $$$[2, 1, 5, 6, 3, 4]$$$, $$$[2, 1, 5, 6, 4, 3]$$$, $$$[2, 1, 6, 5, 3, 4]$$$, $$$[2, 1, 6, 5, 4, 3]$$$. For example, $$$[2, 1, 5, 6, 3, 4]$$$ is good because:

- $$$a_1 = 0$$$, and there are $$$0$$$ values $$$\leq 1$$$ in $$$[p_1] = [2]$$$;
- $$$a_2 = 2$$$, and there are $$$2$$$ values $$$\leq 2$$$ in $$$[p_1, p_2] = [2, 1]$$$;
- $$$a_3 = 2$$$, and there are $$$2$$$ values $$$\leq 3$$$ in $$$[p_1, p_2, p_3] = [2, 1, 5]$$$;
- $$$a_4 = 2$$$, and there are $$$2$$$ values $$$\leq 4$$$ in $$$[p_1, p_2, p_3, p_4] = [2, 1, 5, 6]$$$;
- $$$a_5 = 4$$$, and there are $$$4$$$ values $$$\leq 5$$$ in $$$[p_1, p_2, p_3, p_4, p_5] = [2, 1, 5, 6, 3]$$$;
- $$$a_6 = 6$$$, and there are $$$6$$$ values $$$\leq 6$$$ in $$$[p_1, p_2, p_3, p_4, p_5, p_6] = [2, 1, 5, 6, 3, 4]$$$.

In the third test case, there are no good permutations, because there are no permutations with $$$a_6 = 5$$$ values $$$\leq 6$$$ in $$$[p_1, p_2, p_3, p_4, p_5, p_6]$$$.

Example input:
5
5
1 2 3 4 5
6
0 2 2 2 4 6
6
0 1 3 4 5 5
6
1 2 3 2 4 6
15
0 0 1 1 1 2 3 4 5 6 7 9 11 13 15

Example output:
1
4
0
0
532305727

Editorial:
Small Permutation Problem (Hard Version)
Contest: Pinely Round 3 (Div. 1 + Div. 2)
Difficulty rating: 2500
Tags: combinatorics, dp, math

In the easy version, the $$$a_i$$$ are in the range $$$[0, n]$$$; in the hard version, the $$$a_i$$$ are in the range $$$[-1, n]$$$ and the definition of good permutation is slightly different. You can make hacks only if all versions of the problem are solved.

You are given an integer $$$n$$$ and an array $$$a_1, a_2, \dots, a_n$$$ of integers in the range $$$[-1, n]$$$.

A permutation $$$p_1, p_2, \dots, p_n$$$ of $$$[1, 2, \dots, n]$$$ is good if, for each $$$i$$$, the following condition is true:

- if $$$a_i \neq -1$$$, the number of values $$$\leq i$$$ in $$$[p_1, p_2, \dots, p_i]$$$ is exactly $$$a_i$$$.

Count the good permutations of $$$[1, 2, \dots, n]$$$, modulo $$$998\,244\,353$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \le a_i \le n$$$), which describe the conditions for a good permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single line containing the number of good permutations, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, all the permutations of length $$$5$$$ are good, so there are $$$120$$$ good permutations.

In the second test case, the only good permutation is $$$[1, 2, 3, 4, 5]$$$.

In the third test case, there are $$$4$$$ good permutations: $$$[2, 1, 5, 6, 3, 4]$$$, $$$[2, 1, 5, 6, 4, 3]$$$, $$$[2, 1, 6, 5, 3, 4]$$$, $$$[2, 1, 6, 5, 4, 3]$$$. For example, $$$[2, 1, 5, 6, 3, 4]$$$ is good because:

- $$$a_1 = 0$$$, and there are $$$0$$$ values $$$\leq 1$$$ in $$$[p_1] = [2]$$$;
- $$$a_2 = 2$$$, and there are $$$2$$$ values $$$\leq 2$$$ in $$$[p_1, p_2] = [2, 1]$$$;
- $$$a_3 = 2$$$, and there are $$$2$$$ values $$$\leq 3$$$ in $$$[p_1, p_2, p_3] = [2, 1, 5]$$$;
- $$$a_4 = 2$$$, and there are $$$2$$$ values $$$\leq 4$$$ in $$$[p_1, p_2, p_3, p_4] = [2, 1, 5, 6]$$$;
- $$$a_5 = -1$$$, so there are no restrictions on $$$[p_1, p_2, p_3, p_4, p_5]$$$;
- $$$a_6 = -1$$$, so there are no restrictions on $$$[p_1, p_2, p_3, p_4, p_5, p_6]$$$.

Example input:
10
5
-1 -1 -1 -1 -1
5
1 2 3 4 5
6
0 2 2 2 -1 -1
6
-1 -1 -1 -1 -1 5
6
-1 -1 3 2 -1 -1
15
0 0 -1 -1 -1 2 2 -1 -1 -1 -1 9 11 13 15
6
0 2 2 2 4 6
6
0 1 3 4 5 5
6
1 2 3 2 4 6
15
0 0 1 1 1 2 3 4 5 6 7 9 11 13 15

Example output:
120
1
4
0
0
494403526
4
0
0
532305727

Editorial:
Pumping Lemma
Contest: Pinely Round 3 (Div. 1 + Div. 2)
Difficulty rating: 3000
Tags: hashing, strings

You are given two strings $$$s$$$, $$$t$$$ of length $$$n$$$, $$$m$$$, respectively. Both strings consist of lowercase letters of the English alphabet.

Count the triples $$$(x, y, z)$$$ of strings such that the following conditions are true:

- $$$s = x+y+z$$$ (the symbol $$$+$$$ represents the concatenation);
- $$$t = x+\underbrace{ y+\dots+y }_{k \text{ times}} + z$$$ for some integer $$$k$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n < m \leq 10^7$$$) — the length of the strings $$$s$$$ and $$$t$$$, respectively.

The second line contains the string $$$s$$$ of length $$$n$$$, consisting of lowercase letters of the English alphabet.

The third line contains the string $$$t$$$ of length $$$m$$$, consisting of lowercase letters of the English alphabet.

Output format:
Output a single integer: the number of valid triples $$$(x, y, z)$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Note:
In the first test case, the only valid triple is $$$(x, y, z) = (\texttt{"a"}, \texttt{"bc"}, \texttt{"d"})$$$. In fact,

- $$$\texttt{"abcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"d"}$$$;
- $$$\texttt{"abcbcbcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"d"}$$$.

In the second test case, there are $$$5$$$ valid triples:

- $$$(x, y, z) = (\texttt{""}, \texttt{"a"}, \texttt{"aa"})$$$;
- $$$(x, y, z) = (\texttt{""}, \texttt{"aa"}, \texttt{"a"})$$$;
- $$$(x, y, z) = (\texttt{"a"}, \texttt{"a"}, \texttt{"a"})$$$;
- $$$(x, y, z) = (\texttt{"a"}, \texttt{"aa"}, \texttt{""})$$$;
- $$$(x, y, z) = (\texttt{"aa"}, \texttt{"a"}, \texttt{""})$$$.

In the third test case, there are $$$8$$$ valid triples:

- $$$(x, y, z) = (\texttt{"ab"}, \texttt{"ba"}, \texttt{"babacaab"})$$$;
- $$$(x, y, z) = (\texttt{"abb"}, \texttt{"ab"}, \texttt{"abacaab"})$$$;
- $$$(x, y, z) = (\texttt{"abba"}, \texttt{"ba"}, \texttt{"bacaab"})$$$;
- $$$(x, y, z) = (\texttt{"ab"}, \texttt{"baba"}, \texttt{"bacaab"})$$$;
- $$$(x, y, z) = (\texttt{"abbab"}, \texttt{"ab"}, \texttt{"acaab"})$$$;
- $$$(x, y, z) = (\texttt{"abb"}, \texttt{"abab"}, \texttt{"acaab"})$$$;
- $$$(x, y, z) = (\texttt{"abbaba"}, \texttt{"ba"}, \texttt{"caab"})$$$;
- $$$(x, y, z) = (\texttt{"abba"}, \texttt{"baba"}, \texttt{"caab"})$$$.

Example input:
4 8
abcd
abcbcbcd

Example output:
1

Example input:
3 5
aaa
aaaaa

Example output:
5

Editorial:
Parallel Swaps Sort
Contest: Pinely Round 3 (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: constructive algorithms, data structures

You are given a permutation $$$p_1, p_2, \dots, p_n$$$ of $$$[1, 2, \dots, n]$$$. You can perform the following operation some (possibly $$$0$$$) times:

- choose a subarray $$$[l, r]$$$ of even length;
- swap $$$a_l$$$, $$$a_{l+1}$$$;
- swap $$$a_{l+2}$$$, $$$a_{l+3}$$$ (if $$$l+3 \leq r$$$);
- $$$\dots$$$
- swap $$$a_{r-1}$$$, $$$a_r$$$.

Sort the permutation in at most $$$10^6$$$ operations. You do not need to minimize the number of operations.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the length of the permutation.

The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, the $$$p_i$$$ are distinct) — the permutation before performing the operations.

Output format:
Output your operations in the following format.

The first line should contain an integer $$$k$$$ ($$$0 \le k \le 10^6$$$) — the number of operations.

The next $$$k$$$ lines represent the $$$k$$$ operations in order. Each of these $$$k$$$ lines should contain two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l < r \leq n$$$, $$$r-l+1$$$ must be even) — the corresponding operation consists in choosing the subarray $$$[l, r]$$$ and swapping its elements according to the problem statement.

After all the operations, $$$a_i = i$$$ must be true for each $$$i$$$ ($$$1 \leq i \leq n$$$).

Constraints:
Time limit: 7.0 s
Memory limit: 1024.0 MB

Note:
In the first test:

- At the beginning, $$$p = [2, 5, 4, 1, 3]$$$.
- In the first operation, you can choose $$$[l, r] = [1, 4]$$$. Then, $$$(a_1, a_2)$$$ are swapped and $$$(a_3, a_4)$$$ are swapped. The new permutation is $$$p = [5, 2, 1, 4, 3]$$$.
- In the second operation, you can choose $$$[l, r] = [1, 2]$$$. Then, $$$(a_1, a_2)$$$ are swapped. The new permutation is $$$p = [2, 5, 1, 4, 3]$$$.
- In the third operation, you can choose $$$[l, r] = [2, 5]$$$. Then, $$$(a_2, a_3)$$$ are swapped and $$$(a_4, a_5)$$$ are swapped. The new permutation is $$$p = [2, 1, 5, 3, 4]$$$.
- In the fourth operation, you can choose $$$[l, r] = [1, 4]$$$. Then, $$$(a_1, a_2)$$$ are swapped and $$$(a_3, a_4)$$$ are swapped. The new permutation is $$$p = [1, 2, 3, 5, 4]$$$.
- In the fifth operation, you can choose $$$[l, r] = [4, 5]$$$. Then, $$$(a_4, a_5)$$$ are swapped. The new permutation is $$$p = [1, 2, 3, 4, 5]$$$, which is sorted.

In the second test, the permutation is already sorted, so you do not need to perform any operation.

Example input:
5
2 5 4 1 3

Example output:
5
1 4
1 2
2 5
1 4
4 5

Example input:
9
1 2 3 4 5 6 7 8 9

Example output:
0

Editorial:
Another Sorting Problem
Contest: COMPFEST 13 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1100
Tags: data structures, sortings, strings

Andi and Budi were given an assignment to tidy up their bookshelf of $$$n$$$ books. Each book is represented by the book title — a string $$$s_i$$$ numbered from $$$1$$$ to $$$n$$$, each with length $$$m$$$. Andi really wants to sort the book lexicographically ascending, while Budi wants to sort it lexicographically descending.

Settling their fight, they decided to combine their idea and sort it asc-desc-endingly, where the odd-indexed characters will be compared ascendingly, and the even-indexed characters will be compared descendingly.

A string $$$a$$$ occurs before a string $$$b$$$ in asc-desc-ending order if and only if in the first position where $$$a$$$ and $$$b$$$ differ, the following holds:

- if it is an odd position, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$;
- if it is an even position, the string $$$a$$$ has a letter that appears later in the alphabet than the corresponding letter in $$$b$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \cdot m \leq 10^6$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains a string $$$s_i$$$ consisting of $$$m$$$ uppercase Latin letters — the book title. The strings are pairwise distinct.

Output format:
Output $$$n$$$ integers — the indices of the strings after they are sorted asc-desc-endingly.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
The following illustrates the first example.

Example input:
5 2
AA
AB
BB
BA
AZ

Example output:
5 2 1 3 4

Editorial: