#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1e9 + 7;
bool prime(long long int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
bool isPerfectSquare(long long int x) {
  long double sr = sqrt(x);
  return ((sr - floor(sr)) == 0);
}
bool subsequence_checker(string str1, string str2, long long int m,
                         long long int n) {
  if (m == 0) return true;
  if (n == 0) return false;
  if (str1[m - 1] == str2[n - 1])
    return subsequence_checker(str1, str2, m - 1, n - 1);
  return subsequence_checker(str1, str2, m, n - 1);
}
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
  if (a.first == b.first) return a.second < b.second;
  return (a.first > b.first);
}
void solve() {
  long long int n;
  cin >> n;
  vector<long long int> a;
  for (long long int i = 0; i < n; i++) {
    long long int var;
    cin >> var;
    a.push_back(var);
  };
  stack<long long int> s1, s2;
  long long int sr[n], gr[n], sl[n], gl[n];
  for (long long int i = 0; i < n; i++) {
    while (!s1.empty() and a[s1.top()] >= a[i]) s1.pop();
    if (s1.empty())
      sl[i] = -1;
    else
      sl[i] = s1.top();
    s1.push(i);
  }
  for (long long int i = n - 1; i >= 0; i--) {
    while (!s2.empty() and a[s2.top()] > a[i]) s2.pop();
    if (s2.empty())
      sr[i] = n;
    else
      sr[i] = s2.top();
    s2.push(i);
  }
  while (!s1.empty()) s1.pop();
  while (!s2.empty()) s2.pop();
  long long int mn = 0;
  for (long long int i = 0; i < n; i++) {
    mn += a[i] * ((i - sl[i]) * (sr[i] - i));
  }
  for (long long int i = 0; i < n; i++) {
    while (!s1.empty() and a[s1.top()] <= a[i]) s1.pop();
    if (s1.empty())
      gl[i] = -1;
    else
      gl[i] = s1.top();
    s1.push(i);
  }
  for (long long int i = n - 1; i >= 0; i--) {
    while (!s2.empty() and a[s2.top()] < a[i]) s2.pop();
    if (s2.empty())
      gr[i] = n;
    else
      gr[i] = s2.top();
    s2.push(i);
  }
  long long int mx = 0;
  for (long long int i = 0; i < n; i++) {
    mx += a[i] * ((i - gl[i]) * (gr[i] - i));
  }
  cout << mx - mn;
  return;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int t;
  t = 1;
  while (t--) {
    solve();
    cout << "\n";
  }
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

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>
using namespace std;
const long long int mod = 1e9 + 7;
bool prime(long long int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
bool isPerfectSquare(long long int x) {
  long double sr = sqrt(x);
  return ((sr - floor(sr)) == 0);
}
bool subsequence_checker(string str1, string str2, long long int m,
                         long long int n) {
  if (m == 0) return true;
  if (n == 0) return false;
  if (str1[m - 1] == str2[n - 1])
    return subsequence_checker(str1, str2, m - 1, n - 1);
  return subsequence_checker(str1, str2, m, n - 1);
}
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
  if (a.first == b.first) return a.second < b.second;
  return (a.first > b.first);
}
void solve() {
  long long int n;
  cin >> n;
  vector<long long int> a;
  for (long long int i = 0; i < n; i++) {
    long long int var;
    cin >> var;
    a.push_back(var);
  };
  stack<long long int> s1, s2;
  long long int sr[n], gr[n], sl[n], gl[n];
  for (long long int i = 0; i < n; i++) {
    while (!s1.empty() and a[s1.top()] >= a[i]) s1.pop();
    if (s1.empty())
      sl[i] = -1;
    else
      sl[i] = s1.top();
    s1.push(i);
  }
  for (long long int i = n - 1; i >= 0; i--) {
    while (!s2.empty() and a[s2.top()] > a[i]) s2.pop();
    if (s2.empty())
      sr[i] = n;
    else
      sr[i] = s2.top();
    s2.push(i);
  }
  while (!s1.empty()) s1.pop();
  while (!s2.empty()) s2.pop();
  long long int mn = 0;
  for (long long int i = 0; i < n; i++) {
    mn += a[i] * ((i - sl[i]) * (sr[i] - i));
  }
  for (long long int i = 0; i < n; i++) {
    while (!s1.empty() and a[s1.top()] <= a[i]) s1.pop();
    if (s1.empty())
      gl[i] = -1;
    else
      gl[i] = s1.top();
    s1.push(i);
  }
  for (long long int i = n - 1; i >= 0; i--) {
    while (!s2.empty() and a[s2.top()] < a[i]) s2.pop();
    if (s2.empty())
      gr[i] = n;
    else
      gr[i] = s2.top();
    s2.push(i);
  }
  long long int mx = 0;
  for (long long int i = 0; i < n; i++) {
    mx += a[i] * ((i - gl[i]) * (gr[i] - i));
  }
  cout << mx - mn;
  return;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int t;
  t = 1;
  while (t--) {
    solve();
    cout << "\n";
  }
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}

```