Exchange Students

문제

A group of $nn$ exchange students at Reykjavik University is lining up to get their group photo taken. From left to right, the heights of the students are $g_1,g_2,\dots ,g_{n}g\_1,\; g\_2,\; \backslash ldots,\; g\_n$. However, the photographer would like to rearrange the students such that the order of their heights becomes $h_1,h_2,\dots ,h_{n}h\_1,\; h\_2,\; \backslash ldots,\; h\_n$. In order to do this, the photographer will repeatedly exchange two exchange students. Two exchange students can only be exchanged if they can see each other, that is, if every student in between them has strictly smaller height than the two students to be exchanged.

Determine the minimum number of exchanges needed to arrange the students in the photographer's preferred order, and find a suitable sequence of exchanges of this minimal length. The photographer only has time for at most $2\cdot {10}^{5}2\backslash cdot\; 10^5$ exchanges. If more are needed, you only need to determine the first $2\cdot {10}^{5}2\backslash cdot\; 10^5$ exchanges.

입력

The input consists of:

• One line with an integer $nn$ ($1\le n\le 3\cdot {10}^{5}1\backslash leq\; n\; \backslash leq\; 3\backslash cdot\; 10^5$), the number of students.
• One line with $nn$ integers $g_1,g_2,\dots ,g_{n}g\_1,\; g\_2,\; \backslash ldots,\; g\_n$ ($1\le g_i\le {10}^{9}1\backslash leq\; g\_i\backslash leq\; 10^9$), the heights of the students.
• One line with $nn$ integers $h_1,h_2,\dots ,h_{n}h\_1,\; h\_2,\; \backslash ldots,\; h\_n$ ($1\le h_i\le {10}^{9}1\backslash leq\; h\_i\backslash leq\; 10^9$), the order of heights the photographer prefers.

It is guaranteed that $(h_1,\dots ,h_n)(h\_1,\; \backslash ldots,\; h\_n)$ is a permutation of $(g_1,\dots ,g_n)(g\_1,\; \backslash ldots,\; g\_n)$.

출력

First output an integer $ss$, the minimum number of exchanges needed. Then print $\min (s,2\cdot {10}^5)\backslash min(s,\; 2\backslash cdot\; 10^5)$ exchanges, each consisting of two integers $ii$ and $jj$, the one-based positions of the students that must be exchanged in this step.

If there are multiple valid solutions, you may print any one of them.