Codah ClubTrain. Submit. Improve.
Sign in
English
#000638

Nuclear - Hard

In the Σ-world, there are 1 <= N <= 1,000,000 nuclear reactors, each one has a power index 1 <= Pi < 1,000,000,000. There are exactly N spots on the planet where these reactors can be situated. Additionaly, all these spots lie on a single line. A recent study showed that these reactors have the best combined efficiency when they are arranged such that the sum of absolute differences of powers of every pair of adjacent reactors is minimal. Nuclear reactors are expensive to move so Σ-lets want to know the mimimal number of reactors that need to be resituated to achieve maximum efficiency. Note: The line does not wrap around, it is not a circle. There are N-1 adjacent pairs.


Input First line of input contains a single integer N. The following N lines contain a single integer Pi, the power index of the i-th nuclear reactor. They are given in the order in which they were before the study.

Output Output a single integer, the minimal number of reactors that need to be relocated.

Sample input:
4
3
1
3
6
Sample output:
2

Two reactors (the first and second) should be swapped. The sum then becomes 2+0+3 = 5.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.