← 返回题目列表

AtCoder · abc190_f

F. 移位和反转

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给定的是一个序列 A = [a_0, a_1, a_2, \dots, a_{N-1}] 这是一个排列 0, 1, 2, \dots, N - 1.
对于每个 k = 0, 1, 2, \dots, N - 1,求序列的倒数 B = [b_0, b_1, b_2, \dots, b_{N-1}] 定义为 b_i = a_{i+k \bmod N}.

什么是反转数? 序列的反转数 A = [a_0, a_1, a_2, \dots, a_{N-1}] 是索引对的数量 (i, j) 这样 i < j 和 a_i > a_j.

约束

  • 输入中的所有值都是整数。
  • 2 ≤ N ≤ 3 \times 10^5
  • a_0, a_1, a_2, \dots, a_{N-1} 是一个排列 0, 1, 2, \dots, N - 1.

输入

输入由标准输入按以下格式给出:

N
a_0 a_1 a_2 \cdots a_{N-1}

输出

打印 N 行。
的 (i + 1)- 第行应包含案例的答案 k = i.


示例输入 1

4
0 1 2 3

示例输出 1

0
3
4
3

我们有 A = [0, 1, 2, 3].

对于 k = 0,反转数 B = [0, 1, 2, 3] is 0.
对于 k = 1,反转数 B = [1, 2, 3, 0] is 3.
对于 k = 2,反转数 B = [2, 3, 0, 1] is 4.
对于 k = 3,反转数 B = [3, 0, 1, 2] is 3.


示例输入 2

10
0 3 1 5 4 2 9 6 8 7

示例输出 2

9
18
21
28
27
28
33
24
21
14