2021-01-11 04:00 AKST

Kattis Set 01 - Ad Hoc


2021-01-18 00:30 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -382 days 7:07:05

Time elapsed


Time remaining


Problem C
Physical Music

Picture by: Larry D. Moore

The music business is changing rapidly, and this is reflected by the single charts. Initially, the Dutch Single Top 100 was based purely on sale numbers of CD singles. In the course of time, however, these numbers dropped dramatically, in favour of legal and illegal downloads of music from the internet. Therefore, since 2006, downloads of singles from specific legal downloads sites are incorporated into the chart. Nowadays, even streams from certain streaming platforms contribute to the Single Top 100.

Between 2006 and 2013, when the Single Top 100 was based on both CD singles and downloads, there was also a chart called the Download Top 100, based purely on the downloads. Assuming that both charts used the same numbers of weekly downloads, one could tell from a comparison between the two charts, which singles were selling well physically. And in fact, since some singles did not even appear as CD singles any more, one could tell which singles were certainly available as CD single: the ones that were doing better (as compared to some other singles) in the Single Top 100 than in the Download Top 100.

Now, you are asked to write a program to determine these singles. To be prepared for other communities, which may also have single charts of other sizes, your program should not be limited to charts containing exactly one hundred singles.


The input starts with a line containing an integer $T$ ($1 \leq T \leq 20$), the number of test cases. Then for each test case:

  • One line containing an integer $N$, satisfying $1 \leq N \leq 100\, 000$, the size of both single charts.

  • $N$ lines, each containing a single integer, which together form a permutation of the numbers $1,\ldots ,N$. The $i$-th integer $P_{i}$ is the position in the Download Top $N$ of the single that is ranked $i$ in the Single Top $N$.

As the above specification implies, the Download Top $N$ and the Single Top $N$ contain exactly the same $N$ singles, possibly in different orders.


For each test case, output:

  • One line containing the number of singles $M$ that are certainly available as CD single.

  • $M$ lines, each containing a single integer, the positions of the singles in the Download Top $N$ that are certainly available as CD single, in ascending order.

Sample Input 1 Sample Output 1