Hide

Problem C
Longest Increasing Subsequence

Input

The input consists of several test cases. Each test case begins with a positive integer $n \le 100\, 000$, indicating the length of a sequence. Then follows a sequence of $n$ integers, that fit into 32-bit integer variables.

Output

For each test case, output a line containing the length of a longest increasing subsequence, followed by a line containing the indices of the elements in one such sequence (the first element has index $0$, the second index $1$, and so on). The indices should be given in ascending order.

Sample Input 1 Sample Output 1
10
1 2 3 4 5 6 7 8 9 10
10
1 1 1 1 1 1 1 1 1 1
10
5 19 5 81 50 28 29 1 83 23
10
0 1 2 3 4 5 6 7 8 9
1
7
5
0 1 5 6 8
CPU Time limit 2 seconds
Memory limit 1024 MB
Statistics Show
Author
Per Austrin
Source KTH CSC Popup 2006
License Creative Commons License (cc by)

Please log in to submit a solution to this problem

Log in