该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个 $1\sim n$ 的排列 $a$ .

对于一个整数 $k\in[1,n]$ , 将排列中 $\leqslant k$ 的项构成的子序列建大根笛卡尔树. 这棵笛卡尔树的所有节点的子树大小之和记为 $s_k$ .

$\forall k\in[1,n]$ , 求 $s_k$ .

输入格式

第一行一个整数 $n$，表示排列的长度。

接下来一行 $n$ 个数，表示排列 $a$。

输出格式

输出 $n$ 行，第 $k$ 行的输出为 $s_k$。

样例输入

6
1 2 4 5 6 3

样例输出

1
3
6
8
12
17

数据范围与时空限制

1s，512MB

对于 10% 的数据，$n\leq 100$。

对于 40% 的数据，$n\leq 2000$。

对于另外 10% 的数据，满足 $a_i=i$ 。

对于 100% 的数据，$n\leq 200000$。