Description

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

Input

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

Output

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

Sample Input

Sample Output

Hint

Source