Description

Robert created a segment tree problem. The problem is:

Given a permutation $a_i$ of length $N$, we define a flop operation as swapping the minimum value and the maximum value in an interval. Now you are given $Q$ flop operations; each time you perform a flop operation on $[l,r]$. Find the final sequence after performing the $Q$ flop operations.

After finishing the statement, the next step is to prepare the testdata.

Now you are given $N$, the initial sequence $a_i$, and the final sequence. Find the flop operations to be performed in between.

Input Format

The first line contains an integer representing the length of the sequence $N$.
The second line contains $N$ integers representing the initial sequence $a_i$.
The third line contains $N$ integers representing the final sequence.

Output Format

First, output an integer $Q$, the number of flop operations to perform.
Then output $Q$ lines, each with two integers $l, r$, meaning to perform a flop operation on $[l,r]$.

6
1 3 5 6 4 2
1 2 3 4 5 6

4
2 3
3 6
2 5
4 5

Hint

Sample Explanation

For sample $1$, the $4$ flop operations performed are:

• Perform a flop operation on $[2,3]$, swapping $3$ and $5$.
• Perform a flop operation on $[3,6]$, swapping $6$ and $2$.
• Perform a flop operation on $[2,5]$, swapping $5$ and $2$.
• Perform a flop operation on $[4,5]$, swapping $5$ and $4$.

Constraints

For $100\%$ of the data, $1 \le a_i \le N \le 4096$, $1 \le Q \le 3 \times 10^5$, and $1 \le l \le r \le N$.
For $20\%$ of the data, $N \le 100$.
For another $40\%$ of the data, $N \le 2048$.

Notes

Translated from Canadian Computing Olympiad 2018 Day 2 C Flop Shorting。

Translated by ChatGPT 5