New enemy losses
Limits: 1 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Every morning, every Ukrainian opens the General Staff report to see what losses the enemy suffered during the previous day. Marichka does this too, and in addition, she writes down the data on enemy losses on cards (one number on one card). However, unlike Zenik, every day she writes down the cumulative losses of the enemy from the start of the war.
Marichka recorded the losses every day for \(n\) days, but suddenly noticed that all her cards got mixed up. What a mess! So now her goal is to restore the correct sequence of losses. Since the number of enemy losses grows every day, this is very simple to do!
Zenik, Marichka’s friend, suggested that she lay out all the cards in a row from left to right and perform the following actions: as long as the sequence is not restored, Marichka must choose two adjacent cards such that the difference of the numbers (the number on the left card minus the number on the right) on them is the maximum possible, and swap them. If there are several pairs of cards with the maximum difference, she must choose the leftmost such pair.
For example, if Marichka has cards with numbers \(7\), \(47\), and \(4\), she will act as follows:
swaps cards \(47\) and \(4\), because the difference in this pair \(47 - 4 = 43\) is greater than the difference in the other pair \(7 - 47 = -40\)
swaps cards \(7\) and \(4\), because the difference in this pair \(7 - 4 = 3\) is greater than the difference in the other pair \(4 - 47 = -43\)
Marichka will see that the sequence of enemy losses has become correct (4 enemies on the first day, 3 on the second, and 40 on the third), so she will finish ordering it;
Marichka has already laid out the cards, but she is wondering how long all this action will take. Knowing her abilities, she is confident that it takes her exactly one second to swap two adjacent cards. Moreover, she finds the required pair instantly!
Can you help Marichka calculate how much time she will need to restore the correct sequence?
Input
The first line gives one integer \(n\) — the number of days Marichka recorded statistics for.
The next line gives \(n\) numbers \(a_i\) separated by spaces — the data on cumulative enemy losses according to Marichka’s cards.
Output
Output a single number — how many seconds it will take Marichka to restore the correct sequence of cumulative enemy losses.
Constraints
\(1 \le n \le 5000\),
\(1 \le a_i \le 10^9\),
10 points: \(n \le 100\),
15 points: without additional constraints.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 7 47 4 | 2 |
| Input (stdin) | Output (stdout) |
|---|---|
| 1 146092572 | 0 |
| Input (stdin) | Output (stdout) |
|---|---|
| 5 6 4 3 1 5 | 7 |
Notes
In the second test, the sequence consists of only one card — so it is definitely correct.
In the third test, Marichka will act as follows:
swaps cards with numbers 6 and 4
swaps cards with numbers 6 and 3
swaps cards with numbers 6 and 1
swaps cards with numbers 3 and 1
swaps cards with numbers 4 and 1
swaps cards with numbers 4 and 3
swaps cards with numbers 6 and 5
In total, she will spend 7 seconds on these actions.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|