#P1175. [Balkan2007]The stairways of Saharna

[Balkan2007]The stairways of Saharna

[Balkan2007] The stairways of Saharna

题目描述

给定长度n的正整数序列H。一次选取一条不下降子序列,各次所取的下标不能重复。令L(H,k)为选取k条非空不下降子序列最多覆盖的下标数量。

请依次输出L(H,1),L(H,2),……,L(H,q),其中q为使L(H,q)=n成立的最小整数。必须输出直到首次覆盖全部n个位置,并非固定只输出前三个数。

输入格式

第一行n,第二行n个整数。1≤n≤50001\le n\le5000,1≤Hi≤2551\le H_i\le255。

输出格式

共q行,第k行输出L(H,k)。

12
1 3 4 2 3 4 1 2 2 3 3 2
6
9
12