题目描述

给你一个数字序列，来找最长不下降序列。 比如 $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 \ (1 \le n \le 5000)$，

下面 n 个数字，序列中的每个数 $\le 255$。

输出格式

输出只取一次不下降序列时，最多拿走多少个。

输出只取二次不下降序列时，最多拿走多少个。

输出只取三次不下降序列时，最多拿走多少个。

输入

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

输出

6
9
12