给定一个 $1$ 到 $n$ 的排列，我们可以基于它创建一个包含 $n$ 个顶点的有向图。在这样的图中，只要跳跃过程中经过的元素（不包括起始元素）都小于目标元素，就可以从排列中的任意一个元素跳到另一个元素。这样的图被称为该排列的“跳跃图”（jump graph）。

形式化地，对于顶点 $i$ 到顶点 $j$ ($i \neq j$)，如果 $p_j$ 大于 $i$ 和 $j$ 之间（不包含位置 $i$ 或 $j$）的所有 $p_k$，则存在一条边。换句话说，对于 $i \neq j$，当且仅当对于所有满足 $\min(i, j) < k < \max(i, j)$ 的 $k$，都有 $p_j > p_k$ 时，存在边 $i \to j$。

你的任务是：给定一个排列，对于其跳跃图中的每个顶点，计算它到所有其他顶点的距离之和。从一个顶点到另一个顶点的距离定义为从第一个顶点到第二个顶点的最短路径上的边数。可以证明跳跃图总是强连通的，因此任意两个顶点之间都存在路径。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 300\,000$)，表示排列的长度。

第二行包含一个序列 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$; $p_i \neq p_j$ 当 $i \neq j$)，这是一个 $1$ 到 $n$ 的整数排列。

输出格式

输出一行，包含 $n$ 个整数：第 $i$ 个整数表示从跳跃图的第 $i$ 个顶点到所有其他顶点的距离之和。

样例

输入格式 1

6
1 6 3 2 5 4

输出格式 1

11 7 7 7 6 8

说明

样例排列的跳跃图距离矩阵如下所示。如果从第 $i$ 个顶点到第 $j$ 个顶点存在边，则距离为 $1$（若 $i=j$ 则为 $0$）。