← 返回题目列表

Codeforces · 852/C

C. 属性

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

Bill是BubbleLand中著名的数学家。由于他革命性的数学发现,他能够赚到足够的钱来建造一座漂亮的房子。不幸的是,由于比尔没有按时缴纳财产税,法院决定对比尔进行惩罚,让他失去部分财产。

Bill 的属性可以观察为凸正 2n 边多边形 A0 A1...A2n - 1 A2n, A2n = A0,边长正好为 1 米。

法院关于移走其部分财产的规则如下:

- 将每条边 Ak Ak + 1,  k = 0... 2n - 1 分割为大小为 1 / n 的 n 等份,其中点为 P0, P1, ..., Pn - 1
- 在每条边 A2k A2k + 1,  k = 0... n - 1 法院将为某些 i = 0, ...,  n - 1 选择一个点 B2k =  Pi,使得 $$\bigcup_{i=0}^{n-1} B_{2i} = \bigcup_{i=0}^{n-1} P_i$$
- 在每条边 A2k + 1A2k + 2,  k = 0...n - 1 Bill 将为某些 i = 0, ...,  n - 1 选择一个点 B2k + 1 =  Pi,使得$$\bigcup_{i=0}^{n-1} B_{2i+1} = \bigcup_{i=0}^{n-1} P_i$$
- 比尔可以将财产保留在 2n 边多边形 B0 B1...B2n - 1 内

幸运的是,Bill 发现了法院选择的 B2k 点。尽管他是一位伟大的数学家,但他的房子很大,他很难计算。因此,他要求你帮助他选择点数,以便他最大限度地保留他可以保留的财产面积。

输入

第一行包含一个整数n (2 ≤ n ≤ 50000),表示2n边多边形的边数。

第二行包含 n 个不同的整数 B2k (0 ≤ B2k ≤ n - 1, k = 0... n - 1),用一个空格分隔,代表法院选择的分数。如果 B2k = i,法院选择 A2k A2k + 1 边上的点 Pi。

输出

输出包含 n 个由单个空格分隔的不同整数,代表点 B1、B3、...、B2n - 比尔应选择 1 个整数,以便最大化财产面积。如果有多个解决方案可以最大化面积,则返回其中任何一个。

示例

输入 #1

3
0 1 2

输出 #1

0 2 1

注意

为了最大化面积 Bill 应选择点:B1 = P0、B3 = P2、B5 = P1