Moving Marbles

View as PDF

Submit solution


Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

There are ~n~ marble slots evenly distributed on a circular path. The slots are numbered from ~1~ to ~n~ in the clockwise direction. Additionally, there is a marble holder located at the center of the circular path, numbered ~n+1~.

Initially, with ~n~ marble slots on the circular path, slot ~i~ contains exactly one marble with color ~a_i~, and slot ~n+1~ is empty. The marbles are colored from ~1~ to ~n~, and no two marbles have the same color. You can move a marble from a slot containing a marble to an empty slot if the two slots are adjacent on the circular path, or if one of the slots is slot ~n+1~.

Find a sequence of marble moving operations to rearrange the marbles so that the marble with color ~i~ is in slot ~i~, while the number of operations does not exceed ~1500~.

Input

Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 50~). The description of each test case is as follows.

The first line contains an integer ~n~ (~3 \le n \le 50~) – the number of marble slots on the circular path.

The second line consists of ~n~ integers ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~) – the colors of the marbles in the ~n~ marble slots on the circular path. Each marble color will appear exactly once.

Output

For each test case, output the answer in the following format:

On the first line, output an integer ~k~ (~0 \le k \le 1500~) – the number of marble moving operations to be performed.

On the ~i~-th line in the next ~k~ lines, output two integers ~s_i~ and ~t_i~ (~1 \le s_i, t_i \le n+1~, ~s_i \ne t_i~) describing the moving operation of the ~i~-th marble (from slot ~s_i~ to slot ~t_i~). Slot ~s_i~ must contain a marble, and slot ~t_i~ must be empty.

It can be proven that there always exists a way to rearrange the marbles satisfying the requirements of the problem statement.

Scoring

Subtask Score Constraints
1 ~500~ ~n \le 6~
2 ~500~ ~n \le 25~
3 ~250~ No additional constraints
Total ~1250~

Sample Input 1

2
3
2 3 1
3
1 2 3

Sample Output 1

4
3 4
2 3
1 2
4 1
0

Notes

For the first test case, the diagram below illustrates a way to rearrange the marbles satisfying the requirements of the problem statement. The numbers outside the marble slots indicate the slot numbers, and the numbers inside indicate the color of the marble in the slot.

image

Illustration of the first example.

For the second test case, all marbles are already in their correct slots, so no marble moving operations are needed.


Comments

Please read the guidelines before commenting.



  • 1
    RussVN123  commented on June 17, 2024, 5:38 p.m.

    checker exit -4 là gì thế mọi người. Em nộp lại bài nó bị v.