Bill 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.

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}.

提交代码