[Balkan2007]The stairways of Saharna

给你一个数字序列，请你从中取出不下降子序列。

以序列 $1, 3, 4, 2, 3, 4, 1, 2, 2, 3, 3, 2$ 为例：

• 当只能取一个不下降子序列时，最长的子序列有 $6$ 个数字，例如 $1, 2, 2, 2, 3, 3$；
• 当可以取两个不下降子序列时，一共可以取走 $9$ 个数字：第一次取走 $1, 2, 2, 2, 3, 3$，第二次取走 $3, 4, 4$；
• 当可以取三个不下降子序列时，最多可以取走全部 $12$ 个数字，例如三次分别取走 $1, 3, 4, 4$，$2, 3, 3, 3$，$1, 2, 2, 2$。

输入格式

第一行给出整数 $N$。

以下是 $N$ 个数字。

输出格式

依次输出只取一次、只取两次、只取三次……不下降子序列时，最多能拿走多少个数字，每个答案占一行，直到所有数字都能被取走为止。

样例输入

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

样例输出

6
9
12

数据范围

• $1\le N\le 5000$；
• 每个数字的取值范围为 $[1, 255]$。

来源与许可

本题为 Balkan 2007 试题「The stairways of Saharna」，题面与测试数据整理自 BZOJ 1175。

样例 1

输入

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

输出

6
9
12