背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

给定一个长度为 $N$ 的序列 $A_1, A_2, \dots, A_N$，该序列是 $1$ 到 $N$ 之间的所有整数的一个排列，也就是说，$1$ 到 $N$ 的每个整数恰好出现一次。

$A$ 的一个子序列是通过从 $A$ 中删除 $0$ 个或多个元素得到的序列。

给定三个整数 $x, y, z$（$1 \leq x, y, z \leq N$ 且 $y \leq z$），定义 $f(x, y, z)$ 为满足以下条件的 $A$ 的子序列所能取得的最大长度：

1. 子序列中的元素只能从原序列中下标处于区间 $[y, z]$ 的部分选取。也就是说，子序列只能由 $A_y, A_{y+1}, \dots, A_z$ 组成。
2. 子序列中所有的元素值都不超过 $x$。
3. 子序列必须是一个之字形序列（Zigzag）。

长度为 $K$ 的序列 $S_1, S_2, \dots, S_K$ 是之字形序列，当且仅当对于所有满足 $1 \leq i \leq K - 2$ 的 $i$，满足以下条件之一：

• 如果 $S_i < S_{i+1}$，则有 $S_{i+1} > S_{i+2}$；
• 如果 $S_i > S_{i+1}$，则有 $S_{i+1} < S_{i+2}$。

更具体地说，所有长度不超过 $2$ 的序列都被认为是之字形序列。

请注意，空序列的长度为 $0$，它满足上述所有条件，因此总有 $f(x, y, z) \geq 0$。

现在，对于所有满足 $1 \leq y \leq z \leq N$ 的整数对 $(y, z)$，将所有 $f(x, y, z)$ 的值相加，定义为 $g(x)$。

你的任务是：对于每个 $x = 1, 2, \dots, N$，计算并输出 $g(x)$ 的值。

输入格式

第一行输入一个整数 $N$。
第二行输入 $A_1, A_2, \dots, A_N$，各数之间以空格分隔。

输出格式

输出 $N$ 行，第 $i$ 行输出 $g(i)$ 的值（$1 \leq i \leq N$）。

3
1 2 3

3
7
9

6
3 1 4 6 5 2

10
16
22
34
40
46

提示

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 200\,000$
• 对于所有 $i$（$1 \leq i \leq N$），有 $1 \leq A_i \leq N$；
• 对于所有 $i, j$（$1 \leq i < j \leq N$），有 $A_i \ne A_j$（即 $A$ 是一个排列）。

子任务

1. （10 分）$N \leq 15$
2. （13 分）$N \leq 100$
3. （17 分）$N \leq 500$
4. （22 分）$N \leq 5\,000$
5. （38 分）无附加限制

翻译由 ChatGPT-4o 完成