## CCO '18 P6 - Flop Sorting

View as PDF

Points: 30 (partial)
Time limit: 2.0s
Java 3.0s
Memory limit: 512M
Java 512M
Author:

Problem type

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 distinct integers between and . These are arranged in a row such that the -th integer from the left is , where . 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 flop operations, each specifying two numbers and . For each operation, you must perform a flop on the interval (that is, on the segment of numbers ). You must perform the 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 . The second line will contain distinct space separated integers between and , representing the initial sequence. The third line will also contain distinct space separated integers between and , representing the final sequence.

#### Output Specification

The first line of output should contain the integer , with . The next lines should contain two integers and with .

For 5 of the available 25 marks, .

For an additional 10 of the available 25 marks, .

#### 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.