P12665 [KOI 2023 Round 2] ZigZag

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

给定一个长度为 $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$）。

**限制条件** - 所有输入均为整数。 - $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 完成