题目描述

给你一个数字序列，来找最长不下降序列。

比如 $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$ 个数字。

输出格式

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

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

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

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

6
9
12

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 5000$，$1\le$ 序列中的每个数 $\le 255$。