C. Cakenap Sort
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$a$$$ of length $$$n$$$.

You can perform the following three-step operation on $$$a$$$.

  1. Choose the length $$$k$$$ of a prefix of $$$a$$$ ($$$1\le k \le n$$$).
  2. Reverse the chosen prefix of $$$a$$$.
  3. Move the chosen prefix of $$$a$$$ to the back of $$$a$$$.

For example, here is one possible operation on a permutation of length 10:

Note that if $$$n$$$ is chosen as the length of the prefix, the operation reverses the permutation.

Find a construction using at most $$$2n$$$ operations to sort the permutation $$$a$$$ in ascending order.

It can be shown that this is always possible.

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n \le 5000$$$) — the length of $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le n$$$) — the permutation $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

The first line of output for each test case should contain a single integer $$$q$$$ ($$$0 \le q \le 2n$$$) — the number of operations you will perform.

The second line of output for each test case should contain $$$q$$$ integers — the length of the prefix for each operation you will perform, in order. After these operations, the permutation should be sorted.

If there are multiple solutions, you may print any.

Example
Input
4
3
2 1 3
2
2 1
4
1 4 2 3
10
3 2 1 4 5 6 10 9 8 7
Output
2
2 1
1
2
4
2 3 1 4
6
6 7 6 7 6 7
Note

In the first test case, $$$a$$$ is transformed into $$$[3, 1, 2]$$$ after the first operation, and into $$$[1, 2, 3]$$$ after the second.

In the second test case, $$$a$$$ is transformed into $$$[1, 2]$$$ after the first and only operation.

In the third test case, $$$a$$$ is transformed into $$$[1, 4, 3, 2]$$$ after the first operation, into $$$[2, 3, 4, 1]$$$ after the second, into $$$[4, 3, 2, 1]$$$ after the third, and into $$$[1, 2, 3, 4]$$$ after the fourth.