524 . Trees
Description
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:
, where 
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.
Write a programme 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 Format
There are multiple test cases in the input file, for each test case, first line contains one integer
. Then there are 
integers 
separated by single spaces, denoting the height of the consecutive trees in the row.
Output Format
For each test case the output should consist of precisely lines. The i
th line should contain a single integer - the smallest
disorder coefficient attainable when considering replanting of the i
th tree. There is no need to output any blank lines between test cases.
Sample Input 1
5 7 4 5 2 5 5 1 2 3 4 5
Sample Output 1
7 7 8 7 7 4 4 4 4 4
Hints
In the first example a value 7 of the disorder coefficient may be attained by replanting trees 1 and 4, 2
and 5 or 4 and 5. So, by replanting any of the aforementioned trees (1,2,4,5) and its counterpart a disorder
coefficient of value 7 may be obtained. Only for tree 3 the best possible result is greater - it is 8. In the second
example any replanting increases the value of the disorder coefficient, so no change should take place; all
disorder coefficients have the initial value (4).
Problem Source
Migrated from old NTUJ.
POI14th stage I
Subtasks
| No. | Testdata Range | Score |
|---|