reduceri
Let's consider a row of
N distinct positive integers,
x1, x2, ... xN.
We will call p-reduction eliminating
from one of the two ends of the row the sequence made up of the first or respectively
the last p elements in the row.
More specifically, a p-reduction
consists either of eliminating elements x1,
x2, ...,xp, or eliminating elements xN-p+1,
xN-p+2, ..., xN. Obviously, after the reduction,
the row becomes shorter by p
elements.
The row obtained as a result of the reduction can be the object of other reduction operations of various lengths, the process continuing until the row becomes empty.
The cost of a reduction is calculated as the absolute difference between the elements from the ends of the sequence which are being eliminated times the number of elements in the sequence. Supposing that the reduction is made up of sequence xi, xi+1, ..., xk, then the cost of the reduction is |xi – xk|*(i-k+1). If the reduction is of length 1, then its cost is given by the value of the eliminated element. The total cost of the reductions is given by the sum of all reductions applied to the row.
Task
Determine the maximum cost of all reductions applied to the row.
Input Data
Input file reduceri.in contains on line one positive integer N, and on the following line there are N distinct positive integers each separated by a space, representing the row.
Output Data
File reduceri.out will contain a single line with the total maximum cost that can be obtained by applying successive reductions to the row.
Restrictions and Mentions
3<=N<=100
The row's elements are distinct non-zero positive integers in the 1..1000 interval.
A single reduction resulting in the elimination of the entire row may be applied.
Example
|
reduceri.in |
reduceri.out |
Explanations |
|
6 |
768 |
3 reductions will be made. The first reduction: the first 3 elements are eliminated at a cost of 426. The second reduction: the last element is eliminated at a cost of 118. The last reduction: what is left of the row is eliminated, namely 21 and 133 at a cost of 224. The total cost is 426+118+224=768 |
Time limit: 0.1 seconds/test
prof. Dan Pracsiu
Industrial School Group “Ştefan Procopiu” Vaslui
Contact: dpracsiu@yahoo.com