J. Jesse's Job
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You had one thing to do, one thing! That is the only thing, I might add, that might have saved our lives.
—Walter White, Breaking Bad

Jesse has a permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$. His job is simple: to maximize the number of positions $$$i$$$, for which $$$p_i = i$$$. To achieve that, Jesse can do the following operation exactly once:

  • Color some elements of the permutation in yellow, and all the remaining elements in blue. There has to be at least one yellow and at least one blue element.

  • Then, separately sort yellow and blue numbers.

For example, for permutation $$$(3, 5, 1, 6, 2, 4)$$$, Jesse can mark numbers $$$3, 5, 4$$$ yellow, and $$$1, 6, 2$$$ blue. After sorting yellow and blue elements separately, Jesse will get permutation $$$(3, 4, 1, 2, 6, 5)$$$.

Jesse's score in the end is the number of positions $$$i$$$, for which $$$p_i = i$$$. Find the maximal score Jesse can achieve and some way to achieve it.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$)  — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^6$$$)  — the length of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are distinct)  — elements of the permutation.

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

Output

For every test case, in the first line, output the maximal score Jesse can achieve.

In the second line, output a single integer $$$k$$$ $$$(1 \le k \le n-1)$$$  — the number of elements Jesse should color yellow.

In the third line, output $$$k$$$ integers $$$pos_1, pos_2, \ldots, pos_k$$$ ($$$1 \le pos_i \le n$$$, all $$$pos_i$$$ are distinct)  — the positions of elements that you are going to color in yellow.

If there are several ways to obtain the maximum score, output any of them.

Example
Input
3
2
2 1
4
2 1 4 3
6
3 5 4 2 6 1
Output
0
1
1 
4
2
1 2 
4
3
1 3 4
Note

In the first test case, for permutation $$$(p_1, p_2) = (2, 1)$$$, Jesse can mark $$$p_1$$$ yellow and $$$p_2$$$ blue. After sorting it will remain being $$$(2, 1)$$$, with score $$$0$$$.

In the second test case, for permutation $$$(p_1, p_2, p_3, p_4) = (2, 1, 4, 3)$$$, Jesse can mark $$$p_1, p_2$$$ yellow and $$$p_3, p_4$$$ blue. After sorting the permutation will become $$$(1, 2, 3, 4)$$$, with score $$$4$$$.