萨哈尔纳（Saharna）是摩尔多瓦一个美丽而风景秀丽的地方。在这里的众多洞穴和瀑布中，人们可以找到各种形状和大小的石头。在中世纪，这些石头被用来建造城堡的阶梯。通常，阶梯的每一步都仅由一块石头组成。

这些石头非常重，因此它们的位置沿着一条线固定，即石头按给定的顺序排列。工匠们知道这些石头的高度，因此他们拥有一个整数序列 $H = (h_1, h_2, \dots, h_n)$，其中 $h_i$ 表示第 $i$ 块石头的高度。

为了建造一个阶梯，工匠们沿着这条线移动，并为正在建造的阶梯的每一步依次选择一块石头。显然，只有当一块石头的高度不低于前一块选择的石头的高度时，才能选择该石头。

例如，如果 $H = (1, 3, 4, 2, 3, 4, 1, 2, 2, 3, 3, 2)$，为了建造一个阶梯，可以选择以下序列中带有下划线的石头：

$H = (\underline{1}, \underline{3}, \underline{4}, 2, 3, 4, 1, 2, 2, 3, 3, 2)$

由于越多越好，为了建造更好的城堡，工匠们必须在建造阶梯时使用尽可能多的石头。

我们用 $L(H, k)$ 表示建造 $k$ 个阶梯（每个阶梯至少包含一步）所能使用的最大石头总数。

对于上述例子，不难看出 $L(H, 1) = 6$，即下划线的石头代表了一个最优的阶梯。

类似地，可以验证 $L(H, 2) = 9$，如下面的例子所示，其中第一条阶梯的石头用单下划线表示，第二条阶梯的石头用双下划线表示：

$H = (\underline{\underline{1}}, \underline{3}, \underline{4}, \underline{\underline{2}}, \underline{3}, \underline{4}, \underline{\underline{1}}, \underline{2}, \underline{2}, 3, 3, 2)$

可以看出，对于 $k = 2$，工匠们在第一条阶梯使用了 6 块石头，在第二条阶梯使用了 3 块石头。

如果想要建造 3 个阶梯，可以使用的最大石头数量如以下示例所示：

$H = (\underline{\underline{\underline{1}}}, \underline{3}, \underline{4}, \underline{\underline{2}}, \underline{3}, \underline{4}, \underline{\underline{\underline{1}}}, \underline{2}, \underline{2}, \underline{\underline{\underline{3}}}, \underline{\underline{\underline{3}}}, \underline{\underline{\underline{2}}})$

粗下划线表示第三条阶梯，其他线条含义同上。因此，$L(H, 3) = 12$。可以看到，对于 $k = 3$，第一条阶梯使用了 5 块石头，第二条阶梯使用了 4 块石头，第三条阶梯使用了 3 块石头。请注意，对于 $k = 3$ 所选择的第一和第二条阶梯，与之前情况（$k = 1$ 和 $k = 2$）下选择的阶梯有所不同。

同样显而易见的是，依次取 $k = 1, 2, 3, \dots$，在某一点，对于某个数量 $q$，有 $L(H, q) = n$，其中 $n$ 是石头的总数。

你的任务是帮助中世纪的工匠编写一个程序，在给定高度序列 $H$ 的情况下，计算在 $k$ 个阶梯中可以使用的最大石头数量 $L(H, k)$，其中 $k = 1, 2, \dots, q$。

输入格式

输入的第一行包含一个正整数 $n$。

第二行包含 $n$ 个正整数 $h_1, h_2, \dots, h_i, \dots, h_n$，中间用空格隔开。

输出格式

输出共有 $q$ 行，每行包含一个正整数。第 $k$ 行包含数字 $L(H, k)$，其中 $k = 1, 2, \dots, q$。

样例

输入样例 1

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

输出样例 1

6
9
12

数据范围

$1 \le n \le 5000$；

$1 \le h_i \le 255$，$i = 1, 2, \dots, n$。