Canadian Computing Olympiad: 2018 Day 2, Problem 3

Desperate to contribute to the CCO, Robert tried inventing a segment tree problem. The specification for that problem is:

You are given a list of ~N~ distinct integers between ~1~ and ~N~. These are arranged in a row such that the ~i~-th integer from the left is ~a_i~, where ~1 \le i \le N~. We define a flop operation on a set of elements as swapping the minimum element of the set with the maximum element of the set. There will be ~Q~ flop operations, each specifying two numbers ~l~ and ~r~ ~(1 \le l \le r \le N)~. For each operation, you must perform a flop on the interval ~[l, r]~ (that is, on the segment of numbers ~a_l, a_{l+1}, \dots, a_r~). You must perform the ~Q~ flops in the order given, and report the final result.

Now that he is finished with the problem statement, Robert needs to create some test data. For one test case in particular, he is trying to encode an inside joke into the initial and final sequences of numbers. With these two sequences fixed, help him find any sequence of flop operations that transforms the first sequence into the second.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 4096)~. The second line will contain ~N~ distinct space separated integers between ~1~ and ~N~, representing the initial sequence. The third line will also contain ~N~ distinct space separated integers between ~1~ and ~N~, representing the final sequence.

Output Specification

The first line of output should contain the integer ~Q~, with ~Q \le 300\,000~. The next ~Q~ lines should contain two integers ~l~ and ~r~ with ~1 \le l \le r \le N~.

For 5 of the available 25 marks, ~N \le 100~.

For an additional 10 of the available 25 marks, ~N \le 2048~.

Sample Input

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

Output for Sample Input

4
2 3
3 6
2 5
4 5

Explanation for Output for Sample Input

The first flop swaps 3 and 5, the second flop swaps 6 and 2, the third flop swaps 5 and 2, and the fourth flop swaps 5 and 4.