#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
const int mxN = 1e6 + 5;
template <class T>
T gcd(T a, T b) {
  return ((b == 0) ? a : gcd(b, a % b));
}
int n;
long long a[mxN], s1[4 * mxN], s[4 * mxN];
void build(int id = 1, int l = 0, int r = n) {
  if (r - l < 2) {
    s1[id] = a[l];
    s[id] = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(id * 2, l, mid);
  build(id * 2 + 1, mid, r);
  s[id] = max(s[id * 2], s[id * 2 + 1]);
  s1[id] = min(s1[id * 2], s1[id * 2 + 1]);
}
long long minQ(int x, int y, int id = 1, int l = 0, int r = n) {
  if (x >= r || l >= y) return 1e18;
  if (x <= l && r <= y) return s1[id];
  int mid = (l + r) / 2;
  return min(minQ(x, y, id * 2, l, mid), minQ(x, y, id * 2 + 1, mid, r));
}
long long maxQ(int x, int y, int id = 1, int l = 0, int r = n) {
  if (x >= r || l >= y) return -1e18;
  if (x <= l && r <= y) return s[id];
  int mid = (l + r) / 2;
  return max(maxQ(x, y, id * 2, l, mid), maxQ(x, y, id * 2 + 1, mid, r));
}
long long ans = 0LL;
vector<int> pos[mxN];
void solveMax(int l, int r) {
  if (l >= r) return;
  long long mx = maxQ(l, r);
  int m = (l + r) / 2;
  int l1 = 0, r1 = pos[mx].size() - 1;
  while (l1 < r1) {
    int mid1 = (l1 + r1) / 2;
    if (pos[mx][mid1] >= l)
      r1 = mid1;
    else
      l1 = mid1 + 1;
  }
  int bst = -1;
  if (pos[mx][l1] >= m)
    bst = l1;
  else {
    int l2 = 0, r2 = pos[mx].size() - 1;
    while (l2 < r2) {
      int mid2 = (l2 + r2 + 1) / 2;
      if (pos[mx][mid2] <= m)
        l2 = mid2;
      else
        r2 = mid2 - 1;
    }
    if (l2 == (int)(pos[mx].size() - 1))
      bst = l2;
    else {
      bst = l2;
      if ((pos[mx][l2 + 1] - m) < (m - pos[mx][l2])) bst = l2 + 1;
    }
  }
  assert(bst != -1);
  long long add =
      (long long)(1LL * (pos[mx][bst] - l + 1) * (r - pos[mx][bst]) * mx);
  ans += add;
  if (l < pos[mx][bst]) solveMax(l, pos[mx][bst]);
  if (pos[mx][bst] + 1 < r) solveMax(pos[mx][bst] + 1, r);
}
void solveMin(int l, int r) {
  if (l >= r) return;
  long long mx = minQ(l, r);
  int m = (l + r) / 2;
  int l1 = 0, r1 = pos[mx].size() - 1;
  while (l1 < r1) {
    int mid1 = (l1 + r1) / 2;
    if (pos[mx][mid1] >= l)
      r1 = mid1;
    else
      l1 = mid1 + 1;
  }
  int bst = l1;
  long long sub =
      (long long)(1LL * (pos[mx][bst] - l + 1) * (r - pos[mx][bst]) * mx);
  ans -= sub;
  if (l < pos[mx][bst]) solveMin(l, pos[mx][bst]);
  if (pos[mx][bst] + 1 < r) solveMin(pos[mx][bst] + 1, r);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < (int)(n); i++) cin >> a[i], pos[a[i]].push_back(i);
  build();
  solveMax(0, n);
  solveMin(0, n);
  cout << ans << endl;
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

You are given an array a consisting of n elements. The imbalance value of some subsegment of this array is the difference between the maximum and minimum element from this segment. The imbalance value of the array is the sum of imbalance values of all subsegments of this array.

For example, the imbalance value of array [1, 4, 1] is 9, because there are 6 different subsegments of this array: 

  * [1] (from index 1 to index 1), imbalance value is 0; 
  * [1, 4] (from index 1 to index 2), imbalance value is 3; 
  * [1, 4, 1] (from index 1 to index 3), imbalance value is 3; 
  * [4] (from index 2 to index 2), imbalance value is 0; 
  * [4, 1] (from index 2 to index 3), imbalance value is 3; 
  * [1] (from index 3 to index 3), imbalance value is 0; 



You have to determine the imbalance value of the array a.

Input

The first line contains one integer n (1 ≤ n ≤ 106) — size of the array a.

The second line contains n integers a1, a2... an (1 ≤ ai ≤ 106) — elements of the array.

Output

Print one integer — the imbalance value of a.

Example

Input

3
1 4 1


Output

9

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
const int mxN = 1e6 + 5;
template <class T>
T gcd(T a, T b) {
  return ((b == 0) ? a : gcd(b, a % b));
}
int n;
long long a[mxN], s1[4 * mxN], s[4 * mxN];
void build(int id = 1, int l = 0, int r = n) {
  if (r - l < 2) {
    s1[id] = a[l];
    s[id] = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(id * 2, l, mid);
  build(id * 2 + 1, mid, r);
  s[id] = max(s[id * 2], s[id * 2 + 1]);
  s1[id] = min(s1[id * 2], s1[id * 2 + 1]);
}
long long minQ(int x, int y, int id = 1, int l = 0, int r = n) {
  if (x >= r || l >= y) return 1e18;
  if (x <= l && r <= y) return s1[id];
  int mid = (l + r) / 2;
  return min(minQ(x, y, id * 2, l, mid), minQ(x, y, id * 2 + 1, mid, r));
}
long long maxQ(int x, int y, int id = 1, int l = 0, int r = n) {
  if (x >= r || l >= y) return -1e18;
  if (x <= l && r <= y) return s[id];
  int mid = (l + r) / 2;
  return max(maxQ(x, y, id * 2, l, mid), maxQ(x, y, id * 2 + 1, mid, r));
}
long long ans = 0LL;
vector<int> pos[mxN];
void solveMax(int l, int r) {
  if (l >= r) return;
  long long mx = maxQ(l, r);
  int m = (l + r) / 2;
  int l1 = 0, r1 = pos[mx].size() - 1;
  while (l1 < r1) {
    int mid1 = (l1 + r1) / 2;
    if (pos[mx][mid1] >= l)
      r1 = mid1;
    else
      l1 = mid1 + 1;
  }
  int bst = -1;
  if (pos[mx][l1] >= m)
    bst = l1;
  else {
    int l2 = 0, r2 = pos[mx].size() - 1;
    while (l2 < r2) {
      int mid2 = (l2 + r2 + 1) / 2;
      if (pos[mx][mid2] <= m)
        l2 = mid2;
      else
        r2 = mid2 - 1;
    }
    if (l2 == (int)(pos[mx].size() - 1))
      bst = l2;
    else {
      bst = l2;
      if ((pos[mx][l2 + 1] - m) < (m - pos[mx][l2])) bst = l2 + 1;
    }
  }
  assert(bst != -1);
  long long add =
      (long long)(1LL * (pos[mx][bst] - l + 1) * (r - pos[mx][bst]) * mx);
  ans += add;
  if (l < pos[mx][bst]) solveMax(l, pos[mx][bst]);
  if (pos[mx][bst] + 1 < r) solveMax(pos[mx][bst] + 1, r);
}
void solveMin(int l, int r) {
  if (l >= r) return;
  long long mx = minQ(l, r);
  int m = (l + r) / 2;
  int l1 = 0, r1 = pos[mx].size() - 1;
  while (l1 < r1) {
    int mid1 = (l1 + r1) / 2;
    if (pos[mx][mid1] >= l)
      r1 = mid1;
    else
      l1 = mid1 + 1;
  }
  int bst = l1;
  long long sub =
      (long long)(1LL * (pos[mx][bst] - l + 1) * (r - pos[mx][bst]) * mx);
  ans -= sub;
  if (l < pos[mx][bst]) solveMin(l, pos[mx][bst]);
  if (pos[mx][bst] + 1 < r) solveMin(pos[mx][bst] + 1, r);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < (int)(n); i++) cin >> a[i], pos[a[i]].push_back(i);
  build();
  solveMax(0, n);
  solveMin(0, n);
  cout << ans << endl;
  return 0;
}

```