All submissions for this problem are available.
We all know how being a chef is the most prestigious job in byteland. Motivated by this, almost everyone in byteland wants to become one. As a result, there is a breakout in the number of chefs in town.
The problem arises when they have a get together at the Association of Byte Chefs (ABC) as no chef knows the other chefs. While they are thinking of all the possible ways to solve this problem, Chef Tera comes up with an algorithm.
According to the algorithm, among the N chefs, ith chef will be given a random number (1 <= Ci <= N) and they will stand in a line. Once every one has got their number, the chef standing to the rightmost of the line will start moving left. Whenever he finds a chef having number greater than him, they will introduce themselves to each other. And this will go on till there are no more chefs in the line.
But to Chef Peta, this algorithm doesn’t seem to be the most effective one as even after the completion of it, all the chefs won’t be able to know each other. Just as he was about to point it out, he becomes curious and wants to find out the maximum set of chefs, in which no one knows each other. Since the number N is very large, he won’t be able to do it manually and asks you for help.
Input file starts with T, the number of test cases. Following them are T test cases. Each test case consists of 2 lines. First line contains N, the number of chefs followed by second line containing N space separated integers Ci’s.
Output T lines containing solutions to each test case.
1 <= T <= 10
0 <= N <= 105
0 <= Ci <= N
2 1 3
1 2 3 4
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.