LIS

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Edward has an sequence of n positive integers {a 1 , a 2 , ..., a n }. He soon finds the LIS
(longest increasing subsequence) of the sequence.
But Edward is not satisfied with the result. So he wants to modify an element of the
sequence to another positive integer and make the length of LIS longer.
Now Edward gives the sequence to you, and he wants to know how many elements
can be modified to make the length of LIS longer.
Sequence {s 1 , s 2 , ..., s r } of length r is a subsequence of sequence {a 1 , a 2 , ..., a n }, if
there is such increasing sequence of indexes i 1 , i 2 , ..., i r (1 <=  i 1 < i 2 < ... < i r <= n), that
a i j  = s j .
Sequence {s 1 , s 2 , ..., s r } is increasing, if the following inequality holds: s 1 < s 2 < ...
< s r .

Input

 There are multiple test cases. The first line of input contains an integer T indicating
the number of test cases. For each test case:
The first line contains an integer n (1 <= n <= 100000), indicating the length of the
sequence. The following line contains n integers a 1 , a 2 , ..., a n (1 <= a i <= 10 9 ),
indicating the given sequence.

Output

 For each test case, output an integer s on the first line, indicating the total number of
elements which satisfy the description above. The following line contains s integers p 1 ,
p 2 , ..., p s in increasing order, where p i is the index of the element in the given
sequence (indexes are 1-based).
If s is equal to 0, the second line should be an empty line.

Sample Input

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

Sample Output

0

1
3
2
1 4

Hint

 For the first sample, the length of LIS of original sequence is 3. And no matter which
element we modify the length of LIS won\'t be larger than 3.
For the second sample, the length of LIS of original sequence is 2. We can only
modify 2 to another integer greater than 3, such as 4. So the length of LIS after
modification is 3.

Source

Ningbo_2014_Contest