Start: Apr, 12, 2024 15:00:00
20240412动态规划复习
End: May, 12, 2024 19:00:00
Time elapsed:
Time remaining:

最长上升子序列plus 1856

Time Limit:  1 Sec    Memory Limit:   256 MB
Submission:24     AC:12     Score:100


Description

一个数的序列 $bi$,当 $b1 < b2 < \dots < bS$的时候,我们称这个序列是上升的。

对于给定的一个序列 $(a1, a2, ..., aN)$,我们可以得到一些上升的子序列 $(ai1, ai2, ..., aiK)$,这里 $1 <= i1 < i2 < ... < iK <= N4$。

比如,对于序列 $(1, 7, 3, 5, 9, 4, 8)$,有它的一些上升子序列,如 $(1, 7), (3, 4, 8)$ 等等。

这些子序列中最长的长度是 $4$ ,比如子序列 $(1, 3, 5, 8)$.

你的任务,就是对于给定的序列,求出最长上升子序列的长度,并且输出这个最长上升子序列组成数字的下标

如果存在多组方案,请输出字典序最小的方案

Input

第一行为 $n$ ,表示 $n$ 个数$(10 \leq n \leq 10000)$
第二行 $n$ 个整数,数值之间用一个空格分隔 $(1 \leq a(i) \leq n)$

Output

最长上升子序列的长度

Samples

input:
6 1 6 2 4 4 7
output:
4 1 3 4 6