Hide

# 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

Difficulty
6hard

Statistics
Show

Downloads

Author

Source
KTH CSC Popup 2006