All Submissions


There are n stack of coins placed linearly, each labelled from 1 to n. You also have a sack of coins containing infinite coins with you. All the coins in the stacks and the sack are identical. All you have to do is to make the heights of coins non-decreasing.

You select two stacks i and j and place one coin on each of the stacks of coins from stacki to stackj (inclusive). This complete operations is considered as one move. You have to minimise the number of moves to make the heights non-decreasing.

Input Specification
There will be a number of test cases. Read till EOF. First line of each test case will contain a single integer n, second line contains n heights (hi) of stacks.

Output Specification
Output single integer denoting the number of moves for each test case.

Constraints
No. of Test Cases < 50
1 <= n <= 105
0 <= hi <= 109

Sample Case
Input
3
1 2 3
3
3 2 1
4
7 4 1 47

Output
0
2
6

Explanation
In the first sample case, the heights are already in non-decreasing order.
In the second case, you need to perform two moves
i=2 j=3 H = {3,3,2}
i=3 j=3 H = {3,3,3}

Problem Setter : Shikhar Sharad

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 5 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0