#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 100;
struct Typ {
  int y, w;
  Typ() { y = w = 0; }
  Typ(int a, int b) { y = a, w = b; }
};
int N, A[maxn], B[maxn], o[maxn];
vector<Typ> ope[maxn];
int Tree[maxn];
bool cmp(Typ a, Typ b) { return a.y > b.y; }
int que(int x) {
  int ret = 0;
  for (int i = x; i; i -= (i & (-i))) ret += Tree[i];
  return ret;
}
void add(int x, int v) {
  for (int i = x; i <= N; i += (i & (-i))) Tree[i] += v;
}
long long Done() {
  int t = 0;
  o[t] = 0;
  for (int i = (1), _i = (N); i <= _i; i++) ope[i].clear();
  for (int i = (1), _i = (N); i <= _i; i++) {
    for (; t > 0 && B[i] <= B[o[t]]; t--) {
      ope[o[t - 1] + 1].push_back(Typ(i - 1, o[t]));
    }
    o[++t] = i;
  }
  for (int i = (1), _i = (t); i <= _i; i++)
    ope[o[i - 1] + 1].push_back(Typ(N, o[i]));
  for (int i = (1), _i = (N); i <= _i; i++)
    sort(ope[i].begin(), ope[i].end(), cmp);
  memset(Tree, 0, sizeof(int) * (N + 2));
  long long ret = 0;
  for (int x = (1), _x = (N); x <= _x; x++) {
    for (int i = (0), _i = (ope[x].size() - 1); i <= _i; i++) {
      int y = ope[x][i].y, w = ope[x][i].w;
      int ss = B[w] + que(w);
      ret += ss;
      add(x, -ss);
      add(y + 1, ss);
    }
  }
  return ret;
}
int main(int argc, char* argv[]) {
  for (; scanf("%d", &N) != EOF;) {
    for (int i = (1), _i = (N); i <= _i; i++) scanf("%d", &A[i]);
    int maxf = 0;
    for (int i = (1), _i = (N); i <= _i; i++) {
      maxf = max(maxf, A[i]);
      B[i] = maxf - A[i];
    }
    long long ans = Done();
    printf("%I64d\n", ans);
  }
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

The Little Elephant loves sortings.

He has an array a consisting of n integers. Let's number the array elements from 1 to n, then the i-th element will be denoted as ai. The Little Elephant can make one move to choose an arbitrary pair of integers l and r (1 ≤ l ≤ r ≤ n) and increase ai by 1 for all i such that l ≤ i ≤ r.

Help the Little Elephant find the minimum number of moves he needs to convert array a to an arbitrary array sorted in the non-decreasing order. Array a, consisting of n elements, is sorted in the non-decreasing order if for any i (1 ≤ i < n) ai ≤ ai + 1 holds.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the size of array a. The next line contains n integers, separated by single spaces — array a (1 ≤ ai ≤ 109). The array elements are listed in the line in the order of their index's increasing.

Output

In a single line print a single integer — the answer to the problem.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

3
1 2 3


Output

0


Input

3
3 2 1


Output

2


Input

4
7 4 1 47


Output

6

Note

In the first sample the array is already sorted in the non-decreasing order, so the answer is 0.

In the second sample you need to perform two operations: first increase numbers from second to third (after that the array will be: [3, 3, 2]), and second increase only the last element (the array will be: [3, 3, 3]).

In the third sample you should make at least 6 steps. The possible sequence of the operations is: (2; 3), (2; 3), (2; 3), (3; 3), (3; 3), (3; 3). After that the array converts to [7, 7, 7, 47].

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 100;
struct Typ {
  int y, w;
  Typ() { y = w = 0; }
  Typ(int a, int b) { y = a, w = b; }
};
int N, A[maxn], B[maxn], o[maxn];
vector<Typ> ope[maxn];
int Tree[maxn];
bool cmp(Typ a, Typ b) { return a.y > b.y; }
int que(int x) {
  int ret = 0;
  for (int i = x; i; i -= (i & (-i))) ret += Tree[i];
  return ret;
}
void add(int x, int v) {
  for (int i = x; i <= N; i += (i & (-i))) Tree[i] += v;
}
long long Done() {
  int t = 0;
  o[t] = 0;
  for (int i = (1), _i = (N); i <= _i; i++) ope[i].clear();
  for (int i = (1), _i = (N); i <= _i; i++) {
    for (; t > 0 && B[i] <= B[o[t]]; t--) {
      ope[o[t - 1] + 1].push_back(Typ(i - 1, o[t]));
    }
    o[++t] = i;
  }
  for (int i = (1), _i = (t); i <= _i; i++)
    ope[o[i - 1] + 1].push_back(Typ(N, o[i]));
  for (int i = (1), _i = (N); i <= _i; i++)
    sort(ope[i].begin(), ope[i].end(), cmp);
  memset(Tree, 0, sizeof(int) * (N + 2));
  long long ret = 0;
  for (int x = (1), _x = (N); x <= _x; x++) {
    for (int i = (0), _i = (ope[x].size() - 1); i <= _i; i++) {
      int y = ope[x][i].y, w = ope[x][i].w;
      int ss = B[w] + que(w);
      ret += ss;
      add(x, -ss);
      add(y + 1, ss);
    }
  }
  return ret;
}
int main(int argc, char* argv[]) {
  for (; scanf("%d", &N) != EOF;) {
    for (int i = (1), _i = (N); i <= _i; i++) scanf("%d", &A[i]);
    int maxf = 0;
    for (int i = (1), _i = (N); i <= _i; i++) {
      maxf = max(maxf, A[i]);
      B[i] = maxf - A[i];
    }
    long long ans = Done();
    printf("%I64d\n", ans);
  }
  return 0;
}

```