P6718 [CCO 2018] Flop Sorting

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.

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.

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]$.

#### 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](https://cemc.math.uwaterloo.ca/contests/computing/2018/) Day 2 [C Flop Shorting](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%202/day2.pdf)。 Translated by ChatGPT 5