410597: GYM104064 E Exchange Students

E. Exchange Studentstime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

A group of $$$n$$$ 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, \ldots, g_n$$$. However, the photographer would like to rearrange the students such that the order of their heights becomes $$$h_1, h_2, \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$$$ exchanges. If more are needed, you only need to determine the first $$$2\cdot 10^5$$$ exchanges.

Input

The input consists of:

• One line with an integer $$$n$$$ ($$$1\leq n \leq 3\cdot 10^5$$$), the number of students.
• One line with $$$n$$$ integers $$$g_1, g_2, \ldots, g_n$$$ ($$$1\leq g_i\leq 10^9$$$), the heights of the students.
• One line with $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1\leq h_i\leq 10^9$$$), the order of heights the photographer prefers.

It is guaranteed that $$$(h_1, \ldots, h_n)$$$ is a permutation of $$$(g_1, \ldots, g_n)$$$.Output

First output an integer $$$s$$$, the minimum number of exchanges needed. Then print $$$\min(s, 2\cdot 10^5)$$$ exchanges, each consisting of two integers $$$i$$$ and $$$j$$$, 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.

ExamplesInput

3
2 1 3
3 1 2

Output

1
1 3

Input

5
6 7 5 9 6
9 6 7 6 5

Output

4
3 4
4 5
1 2
1 3