[R74F]编号筛选装置 - 代码源竞赛平台

时空限制

3S/512M

题目描述

研究员正在调试一台栈式筛选装置。装置会依次读取一列互不相同的编号，并按照给定阈值决定将编号压入暂存栈或弹出栈顶。为了比较不同阈值下装置最终保留的编号，需要完成下面的计算。

给定一个长度为 $n$ 的排列$^{\dagger}$ $p_1,p_2,\ldots,p_n$。

对于每个整数阈值 $t=1,2,\ldots,n$，独立执行以下过程：

开始时栈为空。依次处理 $p_1,p_2,\ldots,p_n$：

• 如果 $p_i\le t$，把数值 $p_i$ 放到栈顶。
• 如果 $p_i>t$，则删除当前栈顶的数；若栈为空，什么也不做。

栈只允许从顶部放入或删除数，后放入的数先被删除。处理完整个排列后，求栈中剩余数值之和。空栈的和为 $0$。

请输出每个阈值对应的结果。不同阈值的过程都从空栈重新开始，互不影响。

$^{\dagger}$ :一个长度为 $n$ 的排列是一个包含 $1,2,\dots,n$ 且每个数恰好出现一次的序列。

格式

输入格式

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

第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示要求的排列。

输出格式

输出 $n$ 行，第 $t$ 行表示阈值为 $t$ 时，最终栈中剩余数值之和。

样例

样例输入 #1

5
3 1 5 2 4

样例输出 #1

0
0
3
9
15

样例解释 #1

阈值为 $3$ 时，依次入栈 $3,1$，处理 $5$ 时删除 $1$，随后入栈 $2$，处理 $4$ 时删除 $2$，最终仅剩 $3$。

阈值为 $4$ 时，最后从栈底到栈顶依次为 $3,2,4$，和为 $9$。

样例输入 #2

4
4 3 2 1

样例输出 #2

1
3
6
10

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$30$	$2000$	无
$2$	$20$	$2 \times 10^5$	特殊性质 A
$3$	$50$		无

特殊性质 A：$p_i = i$。

对于 $100\%$ 的数据，满足 $1 \le n \le 2 \times 10^5$ 且 $p$ 是 $1,2,\ldots,n$ 的排列。