问题描述

给定一个 $1$ 至 $n$ 的 排列 $p$。

由排列 $p$ 生成一张包含 $n$ 个点的 边权均为 $1$ 的无向图 $G$，其中 $i,j$ 两点间有边当且仅当 $i<j$ 且 $p_i>p_j$。记 $dis(x,y)$ 表示 $G$ 中 $x,y$ 两点间最短路径的长度，特别地，若 $x,y$ 不连通，$dis(x,y)=0$。

你需要对于图中的每个点 $x$，求出 $\sum_{i=1}^ndis(x,i)$。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $p_1,p_2,\cdots,p_n$，表示排列 $p$。

输出格式

输出一行 $n$ 个整数，第 $i$ 个数表示 $x=i$ 时的答案。

输入样例1

6
3 1 4 2 6 5

输出样例1

4 6 6 4 1 1

样例1解释

$x=1$ 时答案为 $0+1+2+1+0+0=4$。

$x=2$ 时答案为 $1+0+3+2+0+0=6$。

$x=3$ 时答案为 $2+3+0+1+0+0=6$。

$x=4$ 时答案为 $1+2+1+0+0+0=4$。

$x=5$ 时答案为 $0+0+0+0+0+1=1$。

$x=6$ 时答案为 $0+0+0+0+1+0=1$。

数据范围

对于所有数据，保证 $1\le n\le 2\times 10^5$，$1\le p_i\le n$。保证 $p$ 为一个 $1$ 至 $n$ 的排列。

特殊性质 A：保证 $p$ 在所有长为 $n$ 的排列中均匀随机生成。