No tag edit access

C. Property

time limit per test

0.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBill is a famous mathematician in BubbleLand. Thanks to his revolutionary math discoveries he was able to make enough money to build a beautiful house. Unfortunately, for not paying property tax on time, court decided to punish Bill by making him lose a part of his property.

Bill’s property can be observed as a convex regular 2*n*-sided polygon *A*_{0} *A*_{1}... *A*_{2n - 1} *A*_{2n}, *A*_{2n} = *A*_{0}, with sides of the exactly 1 meter in length.

Court rules for removing part of his property are as follows:

- Split every edge
*A*_{k}*A*_{k + 1},*k*= 0... 2*n*- 1 in*n*equal parts of size 1 /*n*with points*P*_{0},*P*_{1}, ...,*P*_{n - 1} - On every edge
*A*_{2k}*A*_{2k + 1},*k*= 0...*n*- 1 court will choose one point*B*_{2k}=*P*_{i}for some*i*= 0, ...,*n*- 1 such that - On every edge
*A*_{2k + 1}*A*_{2k + 2},*k*= 0...*n*- 1 Bill will choose one point*B*_{2k + 1}=*P*_{i}for some*i*= 0, ...,*n*- 1 such that - Bill gets to keep property inside of 2
*n*-sided polygon*B*_{0}*B*_{1}...*B*_{2n - 1}

Luckily, Bill found out which *B*_{2k} points the court chose. Even though he is a great mathematician, his house is very big and he has a hard time calculating. Therefore, he is asking you to help him choose points so he maximizes area of property he can keep.

Input

The first line contains one integer number *n* (2 ≤ *n* ≤ 50000), representing number of edges of 2*n*-sided polygon.

The second line contains *n* distinct integer numbers *B*_{2k} (0 ≤ *B*_{2k} ≤ *n* - 1, *k* = 0... *n* - 1) separated by a single space, representing points the court chose. If *B*_{2k} = *i*, the court chose point *P*_{i} on side *A*_{2k} *A*_{2k + 1}.

Output

Output contains *n* distinct integers separated by a single space representing points *B*_{1}, *B*_{3}, ..., *B*_{2n - 1} Bill should choose in order to maximize the property area. If there are multiple solutions that maximize the area, return any of them.

Example

Input

3

0 1 2

Output

0 2 1

Note

To maximize area Bill should choose points: *B*_{1} = *P*_{0}, *B*_{3} = *P*_{2}, *B*_{5} = *P*_{1}

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/22/2018 03:38:19 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|