TREEOI14 - Trees

Byteasar has a cottage. Lately, he has bought n trees and had them planted all in one row. Byteasar does not, however, like the order which the trees have been planted in. It particularly annoys him that tall and short ones have been mixed up, and the composition does not meet his aesthetic criteria.

Byteasar has invented a disorder coefficient so as to allow the gardener to comprehend his intentions: the lower the value of the coefficient the prettier the row of trees. It is defined in the following way: |h1−h2|+ |h2−h3|+...+|hn−1−hn|, where h1,h2, . . . ,hn are the heights of consecutive trees in a row.

Replanting is a very toilsome and cumbersome task, therefore Byteasar has ordered the gardener to replant two trees at the most (i.e. interchange their positions). The task of the gardener is to choose the pair to replant in a way that makes the disorder coefficient the smallest.

The gardener is not sure if he has chosen the correct pair of trees and he fears he may lose his job if he is mistaken. Help him: for each tree calculate the minimal disorder coefficient that may be attained by switching places with any other tree.

Task

Write a program which:

  • reads the height of the consecutive trees in a row from the standard input,
  • for each tree calculates the minimal disorder coefficient that may be attained should it switch places with some other tree (or should there be no change at all),
  • writes the outcome to the standard output.

Input

The first line of the standard input contains one integer n (2 <= n <= 50000). The other contains n integers hi (1 <= hi <= 100000000) separated by single spaces, denoting the height of the consecutive trees in the row.

Output

The output should consist of precisely n lines. The i-th line should contain a single integer - the smallest disorder coefficient attainable when considering replanting of the i-th tree.

Example

Input:
5
7 4 5 2 5

Output:
7
7
8
7
7
* Added some unofficial tests

Added by:Thanh-Vy Hua
Date:2007-06-09
Time limit:0.206s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Polish Olympiad 14

hide comments
2023-09-09 23:23:28 Oleg
Awesome problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.