Sorting#7770

Sorting

1 second

128 megabytes

Very easy

Aizhan has a sequence of $n$ integers $S_{0}, S_{1}, ..., S_{n - 1}$ S_0, S_1, ..., S_{n-1}. This sequence consists of distinct numbers from $0$ to $n - 1$ n - 1. Aizhan is trying to sort this sequence in increasing order by swapping some pairs of elements. Her friend Ermek will also perform some swaps, but there is no guarantee that he will do it in a useful way.

Ermek and Aizhan will modify the sequence in several stages. At each stage, Ermek performs a swap first, and then Aizhan performs another swap. More precisely, the one who performs a swap chooses two valid positions and swaps the elements at those positions. Note that the two positions do not have to be different. If they are the same, the element is swapped with itself, and the sequence remains unchanged.

Aizhan knows that Ermek does not care about sorting the sequence $S$ . She knows exactly which positions Ermek will choose. Ermek plans to participate in $m$ stages. The stages are numbered from $0$ to $m - 1$ m - 1. For all $i$ from $0$ to $m - 1$ m - 1 inclusive, Ermek will choose positions $x_{i}$ x_i and $y_{i}$ y_i at stage $i$ .

Aizhan wants to sort the sequence $S$ . Before the start of each stage, if Aizhan sees that the sequence is already sorted in increasing order, the whole process stops. Given the initial sequence $S$ and the positions that Ermek is going to choose, you need to find a sequence of swaps that Aizhan can use to sort the sequence $S$ . In some subtasks, it is required to find the shortest possible sequence of swaps. It is guaranteed that the sequence $S$ can be sorted in $m$ or fewer stages.

If Aizhan sees that the sequence $S$ is sorted after the swap performed by Ermek, she may choose a swap with equal positions (for example, $0$ and $0$ ). As a result, the sequence $S$ will remain sorted after the stage ends, and Aizhan will achieve her goal. Also note that if the sequence $S$ is initially sorted, then the minimum number of stages required is $0$ .

Given the sequence $S$ , the number of swaps $m$ , and the sequences of positions $X$ and $Y$ , find a sequence of swaps that Aizhan can use to sort the sequence $S$ .

Input

The first line contains the length of the sequence $S$ .

The second line contains the initial sequence $S_{0}, S_{1}, ..., S_{n - 1} (n \leq 200000)$ S_0, S_1, ..., S_{n-1}~(n \le 200000).

The next line contains the number of swaps $m (m \leq 3 \cdot n)$ m~(m \le 3 \cdot n) planned by Ermek.

Each of the following $m$ lines contains a pair of integers $x_{i}$ x_i and $y_{i}$ y_i. They mean that at stage $i$ $(0 \leq i \leq m - 1)$ (0 \le i \le m - 1) Ermek plans to swap the elements at positions $x_{i}$ x_i and $y_{i}$ y_i.

Output

In the first line, print the number of swaps $R$ made by Aizhan.

In the next $R$ lines, print the sequence of swaps of minimal length that Aizhan can use to sort $S$ .

Each line should contain a pair of positions $p_{i}$ p_i and $q_{i}$ q_i to be swapped.

Examples

Example 1. Suppose that:

Initial sequence: $S = 4, 3, 2, 1, 0$ S = 4, 3, 2, 1, 0.
Ermek is going to perform six swaps $(m = 6)$ (m = 6).
The sequences $X$ and $Y$ describing the positions Ermek will choose are: $X = 0, 1, 2, 3, 0, 1$ X = 0, 1, 2, 3, 0, 1 and $Y = 1, 2, 3, 4, 1, 2$ Y = 1, 2, 3, 4, 1, 2. That is, the pairs of positions Ermek plans to choose are $(0, 1), (1, 2), (2, 3), (3, 4), (0, 1)$ (0, 1), (1, 2), (2, 3), (3, 4), (0, 1) and $(1, 2)$ .

In this case, Aizhan can transform the sequence $S$ into $0, 1, 2, 3, 4$ 0, 1, 2, 3, 4 in three stages. She can do this by choosing positions $(0, 4), (1, 3)$ (0, 4), (1, 3), and then $(3, 4)$ . The following table shows how Ermek and Aizhan modify the sequence $S$ .

Example 2. Suppose that:

Initial sequence: $S = 3, 0, 4, 2, 1$ S = 3, 0, 4, 2, 1.
Ermek is going to perform five swaps $(m = 5)$ (m = 5).
The pairs of positions Ermek plans to choose are: $(1, 1), (4, 0), (2, 3), (1, 4)$ (1, 1), (4, 0), (2, 3), (1, 4) and $(0, 4)$ .

In this case, Aizhan can sort the sequence $S$ in three stages, for example by choosing pairs $(1, 4), (4, 2)$ (1, 4), (4, 2), and then $(2, 2)$ . The following table shows how Ermek and Aizhan modify the sequence $S$ .

Example 1

Example 2