#include <bits/stdc++.h>
int main() {
  int a[200000];
  int N;
  int i, j;
  unsigned long long ans = 0;
  unsigned long long *minwa;
  int prev;
  minwa = (unsigned long long *)calloc(200000, sizeof(unsigned long long));
  scanf("%d", &N);
  for (i = 0; i < N; i++) {
    std::cin >> a[i];
  }
  prev = a[0];
  for (i = 0; i < N; i++) {
    unsigned long long wa = 0;
    int min = a[i];
    for (j = 0; j < N - i; j++) {
      if (min > a[i + j]) {
        min = a[i + j];
      }
      if (prev < min) {
        if (minwa[prev] != 0) {
          minwa[prev] -= prev;
        }
      } else if (minwa[prev] != 0) {
        wa += minwa[prev];
        break;
      }
      wa += min;
    }
    prev = a[i];
    minwa[prev] = wa - a[i];
    ans += wa;
  }
  printf("%u\n", ans);
  return 0;
}
