[Balkan2007]The stairways of Saharna

时间限制:4s      空间限制:162MB

题目描述

给你一个数字序列,来找最长不下降序列.比如 1; 3; 4; 2; 3; 4; 1; 2; 2; 3; 3; 2 当只取一个不下降序列时,最长的序列为六个.其为1;2;2;2;3;3 当可以取两个不下降序列时,一共可以取走九个数字. 你可以第一次取走1;2;2;2;3;3 第二次取走3;4;4 当可以取三个不下降序列,最多可以取走12个数字. 第一次取走1;2;3;3;3 第二次取走1;2;2; 第三次取走3;4;4


输入格式

第一行给出数字N,N在[1,5000] 下面N个数字.值在[1,255]


输出格式

输出只取一次不下降序列时,最多拿走多少个. 输出只取二次不下降序列时,最多拿走多少个. 输出只取三次不下降序列时,最多拿走多少个. ......................................


样例输入

12
1 3 4 2 3 4 1 2 2 3 3 2

样例输出

6
9
12

提示

没有写明提示


题目来源

没有写明来源