#1175. [Balkan2007]The stairways of Saharna

内存限制:162 MiB 时间限制:4 Sec

题目描述

给你一个数字序列,来找最长不下降序列.比如 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

数据范围与提示