#P18425. Jump Graph

Jump Graph

Jump Graph

给定一个 11 到 nn 的排列,可以用它构造一个有 nn 个顶点的有向图。若从排列的某个位置跳向另一个位置时,中间跳过的所有元素都小于目标位置的元素,就允许这次跳跃;不比较起点的元素。这种图称为该排列的跳跃图。

形式化地,对于 i≠ji\ne j,当且仅当对所有满足

min⁡(i,j)<k<max⁡(i,j)\min(i,j)<k<\max(i,j)

的下标 kk 都有 pj>pkp_j>p_k 时,图中存在有向边 i→ji\to j。起点和终点均不属于中间下标。

对于每个顶点,求从它出发到所有其他顶点的最短距离之和。两个顶点间的距离指有向最短路径的边数。可以证明跳跃图总是强连通,所以任意两个顶点之间都存在有向路径。

输入格式

第一行包含一个整数 nn,满足 2≤n≤3000002\le n\le300000,表示排列长度。

第二行包含 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n。保证 1≤pi≤n1\le p_i\le n,且 i≠ji\ne j 时 pi≠pjp_i\ne p_j。

输出格式

输出一行 nn 个整数。第 ii 个数表示跳跃图中从顶点 ii 到所有其他顶点的最短距离之和。

样例

输入:

6
1 6 3 2 5 4

输出:

11 7 7 7 6 8

样例说明

原题给出的表如下:

原题样例距离表

第 ii 行、第 jj 列是从 ii 到 jj 的有向最短距离,每行之和就是相应的输出。

原 PDF 的说明将此表称为“邻接矩阵”,并描述成仅含 0/10/1;但原表实际含有 2,32,3,逐对按题面正式边定义建图并进行 BFS 得到的恰好是此距离表,且各行之和与完整原样例一致。因此这里更正表名,保留原表像素;边的定义和题目要求均未改变。