https://www.acmicpc.net/problem/28327

# KOI 23 Zig Zag

Given is a sequence $A_1, A_2, \ldots, A_N$ of length $N$. This sequence contains integers from $1$ to $N$ exactly once.

A subsequence of $A$ refers to a sequence obtained by removing zero or more elements from sequence $A$. Let three integers $x, y, z$ ($1 \le x, y, z \le N$, $y \le z$) be given. Let $f(x, y, z)$ represent the maximum length that a subsequence of $A$ can have, satisfying the following conditions:

- The elements in the subsequence must have their original positions in the interval $[y, z]$. In other words, the subsequence can only consist of elements $A_y, A_{y + 1}, \ldots, A_z$.
- The value of each element in the subsequence must be less than or equal to $x$
- The subsequence must be a zigzag sequence. A sequence $S_1, \ldots, S_K$ of length $K$ is considered a zigzag sequence if, for each $i$ ($1 \le i \le K-2$), $S_i < S_{i+1}$ implies $S_{i+1} > S_{i+2}$, and $S_i > S_{i+1}$ implies $S_{i+1} < S_{i+2}$. Specifically, sequences of length 2 or less are all considered zigzag sequences.

Note that an empty sequence of length 0 satisfies all three conditions, so $f(x, y, z) \geq 0$ always holds.

Define $g(x)$ as the sum of all $f(x, y, z)$ for all integers $y, z$ satisfying $1 \le y \le z \le N$. Write a program to calculate the values of $g(1), g(2), \ldots, g(N)$.

# Input

The first line contains an integer $N$.

The second line contains $N$ integers $A_1, A_2, \dots, A_N$ separated by a space.

# Output

Print $N$ lines. In the $i$ ($1 \le i \le N$)-th line, output the value of $g(i)$.

# Constraints

- All given numbers are integers.
- $2 \le N \le 200,000$
- For all $i$ ($1 \le i \le N$), $1 \le A_i \le N$.
- For all $i, j$ ($1 \le i < j \le N$), $A_i \neq A_j$.

# Subtasks


See the original statement for samples