There is a large number of empty bins in a factory depot. The bins are arranged in a single
row. The manager of the depot wants to put some bins into other bins to make some free space
in the left end of the depot. Bins can be moved by a robot, which can take a bin, carry it to
the right, and put it into a larger bin. This three-operation sequence is the only allowed way to
move bins.
Because of safety regulations, any bin can contain at most one other bin, which must be empty.
The manager also wants to keep the double bins in the left end of the resulting row, to make it
easier to keep track of them.
You are to write a program that computes the largest possible K such that the K leftmost bins
can be put into the immediately following K bins in some order.
The first line of the input contains an integer T indicating the number of test cases. For each test case, the first line contains two integers, separated by a space: M (1 ≤ M ≤ 1000), the size of the largest bin, and N (1 ≤ N ≤ 20,000), the number of bins. The second line contains N integers Ai (1 ≤ Ai ≤ M), separated by spaces: the sizes of the bins,
listed from left to right.
For each test case output a line containing a single integer, the
largest number K such that the robot can put the K leftmost bins into the next K bins.
1 5 10 2 2 1 4 3 2 5 4 2 3
4
Migrated from old NTUJ.
BOI2010
| No. | Testdata Range | Score |
|---|