Jesse's Job

Time limit: 1s Memory limit: 256MB Input: 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 p1,p2,,pnp_1, p_2, \ldots, p_n of integers from 11 to nn. His job is simple: to maximize the number of positions ii, for which pi=ip_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)(3, 5, 1, 6, 2, 4), Jesse can mark numbers 3,5,43, 5, 4 yellow, and 1,6,21, 6, 2 blue. After sorting yellow and blue elements separately, Jesse will get permutation (3,4,1,2,6,5)(3, 4, 1, 2, 6, 5).

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

Input data

The first line contains a single integer tt (1t1051 \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 nn (2n1062 \leq n \leq 10^6) - the length of the permutation.

The second line of each test case contains nn integers p1,p2,,pnp_1, p_2, \ldots, p_n (1pin1 \le p_i \le n, all pip_i are distinct) - elements of the permutation.

It is guaranteed that the sum of nn over all test cases does not exceed 10610^6.

Output data

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

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

In the third line, output kk integers pos1,pos2,,poskpos_1, pos_2, \ldots, pos_k (1posin1 \le pos_i \le n, all posipos_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

stdin

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

stdout

0
1
1 
4
2
1 2 
4
3
1 3 4 

Explanation

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

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

Log in or sign up to be able to send submissions!