#include <bits/stdc++.h>
using namespace std;
struct fast_ios {
  fast_ios() {
    cin.tie(nullptr), ios::sync_with_stdio(false),
        cout << fixed << setprecision(20);
  };
} fast_ios_;
template <class T>
auto add = [](T a, T b) -> T { return a + b; };
template <class T>
auto f_max = [](T a, T b) -> T { return max(a, b); };
template <class T>
auto f_min = [](T a, T b) -> T { return min(a, b); };
template <class T>
using V = vector<T>;
using Vl = V<long long int>;
using VVl = V<Vl>;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (int i = 0; i < (int)v.size(); i++)
    os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& in : v) is >> in;
  return is;
}
template <class T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
long long int gcd(long long int a, long long int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long int ceil(long long int a, long long int b) { return (a + b - 1) / b; }
long long int digit(long long int a) { return (long long int)log10(a); }
long long int e_dist(pair<long long int, long long int> a,
                     pair<long long int, long long int> b) {
  return abs(a.first - b.first) * abs(a.first - b.first) +
         abs(a.second - b.second) * abs(a.second - b.second);
}
long long int m_dist(pair<long long int, long long int> a,
                     pair<long long int, long long int> b) {
  return abs(a.first - b.first) + abs(a.second - b.second);
}
bool check_overflow(long long int a, long long int b, long long int limit) {
  if (b == 0) return false;
  return a > limit / b;
}
void Worshall_Floyd(VVl& g) {
  for (long long int k = (0), k_end_ = (((long long int)(g).size()));
       k < k_end_; ++k)
    for (long long int i = (0), i_end_ = (((long long int)(g).size()));
         i < i_end_; ++i)
      for (long long int j = (0), j_end_ = (((long long int)(g).size()));
           j < j_end_; ++j)
        chmin(g[i][j], g[i][k] + g[k][j]);
}
const long long int MOD1000000007 = 1000000007, MOD998244353 = 998244353,
                    INF = 5e18;
long long int dx[8] = {1, 0, -1, 0, 1, -1, 1, -1},
              dy[8] = {0, 1, 0, -1, -1, -1, 1, 1};
bool YN(bool flag) {
  cout << (flag ? "YES" : "NO") << '\n';
  return flag;
}
bool yn(bool flag) {
  cout << (flag ? "Yes" : "No") << '\n';
  return flag;
}
struct Edge {
  long long int from, to;
  long long int cost;
  Edge() {}
  Edge(long long int u, long long int v, long long int c) {
    cost = c;
    from = u;
    to = v;
  }
  bool operator<(const Edge& e) const { return cost < e.cost; }
};
struct WeightedEdge {
  long long int to;
  long long int cost;
  WeightedEdge(long long int v, long long int c = 1) {
    to = v;
    cost = c;
  }
  bool operator<(const WeightedEdge& e) const { return cost < e.cost; }
};
using WeightedGraph = V<V<WeightedEdge>>;
struct BinaryIndexedTree {
  int n;
  int b;
  vector<long long int> bit;
  BinaryIndexedTree(int n_) : n(n_ + 1), bit(n, 0) {}
  void add(int i, long long int x) {
    for (int idx = i; idx < n; idx += (idx & -idx)) {
      bit[idx] += x;
    }
  }
  long long int sum(int i) {
    long long int s = 0;
    for (int idx = i; idx > 0; idx -= (idx & -idx)) {
      s += bit[idx];
    }
    return s;
  }
  int lower_bound(long long int w) {
    if (w <= 0) {
      return 0;
    } else {
      int x = 0, r = 1;
      while (r < n) r = r << 1;
      for (int len = r; len > 0; len = len >> 1) {
        if (x + len < n && bit[x + len] < w) {
          w -= bit[x + len];
          x += len;
        }
      }
      return x;
    }
  }
  void show() {
    for (int i = 0; i < n - 1; i++) {
      cout << sum(i) - sum(i - 1) << " ";
    }
    cout << '\n';
  }
};
struct ExtendBinaryIndexedTree {
 public:
  ExtendBinaryIndexedTree(int _n) { init(_n); }
  void add(int l, int r, long long int x) {
    add_sub(0, l, -x * (l - 1));
    add_sub(0, r, x * (r - 1));
    add_sub(1, l, x);
    add_sub(1, r, -x);
  }
  long long int sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; }
  void show() {
    for (int i = 0; i < n - 1; i++) {
      cout << sum(i + 1) - sum(i) << " ";
    }
    cout << '\n';
  }

 private:
  int n;
  vector<long long int> bit[2];
  void init(int _n) {
    n = _n + 1;
    bit[0].assign(n, 0);
    bit[1].assign(n, 0);
  }
  void add_sub(int p, int i, long long int x) {
    for (int idx = i; idx < n; idx += (idx & -idx)) {
      bit[p][idx] += x;
    }
  }
  long long int sum_sub(int p, int i) {
    long long int s = 0;
    for (int idx = i; idx > 0; idx -= (idx & -idx)) {
      s += bit[p][idx];
    }
    return s;
  }
};
long long int N;
int main() {
  cin >> N;
  Vl arr(N);
  cin >> arr;
  VVl poses(1e6);
  for (long long int i = (0), i_end_ = (N); i < i_end_; ++i) {
    arr[i]--;
    poses[arr[i]].push_back(i + 1);
  }
  long long int ans = 0;
  {
    BinaryIndexedTree tree(N);
    for (long long int k = (0), k_end_ = (1e6); k < k_end_; ++k) {
      for (long long int p : poses[k]) {
        tree.add(p, 1);
        long long int l, r;
        if (tree.sum(p) == 1) {
          l = -1;
        } else {
          l = tree.lower_bound(tree.sum(p) - 1);
        }
        r = tree.lower_bound(tree.sum(p) + 1);
        ans -= (p - l - 1) * (r - p + 1) * k;
      }
    }
  }
  {
    BinaryIndexedTree tree(N);
    for (long long int k = (1e6) - 1, k_begin_ = (0); k >= k_begin_; --k) {
      for (long long int p : poses[k]) {
        tree.add(p, 1);
        long long int l, r;
        if (tree.sum(p) == 1) {
          l = -1;
        } else {
          l = tree.lower_bound(tree.sum(p) - 1);
        }
        r = tree.lower_bound(tree.sum(p) + 1);
        ans += (p - l - 1) * (r - p + 1) * k;
      }
    }
  }
  cout << ans << '\n';
}

### 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>
using namespace std;
struct fast_ios {
  fast_ios() {
    cin.tie(nullptr), ios::sync_with_stdio(false),
        cout << fixed << setprecision(20);
  };
} fast_ios_;
template <class T>
auto add = [](T a, T b) -> T { return a + b; };
template <class T>
auto f_max = [](T a, T b) -> T { return max(a, b); };
template <class T>
auto f_min = [](T a, T b) -> T { return min(a, b); };
template <class T>
using V = vector<T>;
using Vl = V<long long int>;
using VVl = V<Vl>;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (int i = 0; i < (int)v.size(); i++)
    os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& in : v) is >> in;
  return is;
}
template <class T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
long long int gcd(long long int a, long long int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long int ceil(long long int a, long long int b) { return (a + b - 1) / b; }
long long int digit(long long int a) { return (long long int)log10(a); }
long long int e_dist(pair<long long int, long long int> a,
                     pair<long long int, long long int> b) {
  return abs(a.first - b.first) * abs(a.first - b.first) +
         abs(a.second - b.second) * abs(a.second - b.second);
}
long long int m_dist(pair<long long int, long long int> a,
                     pair<long long int, long long int> b) {
  return abs(a.first - b.first) + abs(a.second - b.second);
}
bool check_overflow(long long int a, long long int b, long long int limit) {
  if (b == 0) return false;
  return a > limit / b;
}
void Worshall_Floyd(VVl& g) {
  for (long long int k = (0), k_end_ = (((long long int)(g).size()));
       k < k_end_; ++k)
    for (long long int i = (0), i_end_ = (((long long int)(g).size()));
         i < i_end_; ++i)
      for (long long int j = (0), j_end_ = (((long long int)(g).size()));
           j < j_end_; ++j)
        chmin(g[i][j], g[i][k] + g[k][j]);
}
const long long int MOD1000000007 = 1000000007, MOD998244353 = 998244353,
                    INF = 5e18;
long long int dx[8] = {1, 0, -1, 0, 1, -1, 1, -1},
              dy[8] = {0, 1, 0, -1, -1, -1, 1, 1};
bool YN(bool flag) {
  cout << (flag ? "YES" : "NO") << '\n';
  return flag;
}
bool yn(bool flag) {
  cout << (flag ? "Yes" : "No") << '\n';
  return flag;
}
struct Edge {
  long long int from, to;
  long long int cost;
  Edge() {}
  Edge(long long int u, long long int v, long long int c) {
    cost = c;
    from = u;
    to = v;
  }
  bool operator<(const Edge& e) const { return cost < e.cost; }
};
struct WeightedEdge {
  long long int to;
  long long int cost;
  WeightedEdge(long long int v, long long int c = 1) {
    to = v;
    cost = c;
  }
  bool operator<(const WeightedEdge& e) const { return cost < e.cost; }
};
using WeightedGraph = V<V<WeightedEdge>>;
struct BinaryIndexedTree {
  int n;
  int b;
  vector<long long int> bit;
  BinaryIndexedTree(int n_) : n(n_ + 1), bit(n, 0) {}
  void add(int i, long long int x) {
    for (int idx = i; idx < n; idx += (idx & -idx)) {
      bit[idx] += x;
    }
  }
  long long int sum(int i) {
    long long int s = 0;
    for (int idx = i; idx > 0; idx -= (idx & -idx)) {
      s += bit[idx];
    }
    return s;
  }
  int lower_bound(long long int w) {
    if (w <= 0) {
      return 0;
    } else {
      int x = 0, r = 1;
      while (r < n) r = r << 1;
      for (int len = r; len > 0; len = len >> 1) {
        if (x + len < n && bit[x + len] < w) {
          w -= bit[x + len];
          x += len;
        }
      }
      return x;
    }
  }
  void show() {
    for (int i = 0; i < n - 1; i++) {
      cout << sum(i) - sum(i - 1) << " ";
    }
    cout << '\n';
  }
};
struct ExtendBinaryIndexedTree {
 public:
  ExtendBinaryIndexedTree(int _n) { init(_n); }
  void add(int l, int r, long long int x) {
    add_sub(0, l, -x * (l - 1));
    add_sub(0, r, x * (r - 1));
    add_sub(1, l, x);
    add_sub(1, r, -x);
  }
  long long int sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; }
  void show() {
    for (int i = 0; i < n - 1; i++) {
      cout << sum(i + 1) - sum(i) << " ";
    }
    cout << '\n';
  }

 private:
  int n;
  vector<long long int> bit[2];
  void init(int _n) {
    n = _n + 1;
    bit[0].assign(n, 0);
    bit[1].assign(n, 0);
  }
  void add_sub(int p, int i, long long int x) {
    for (int idx = i; idx < n; idx += (idx & -idx)) {
      bit[p][idx] += x;
    }
  }
  long long int sum_sub(int p, int i) {
    long long int s = 0;
    for (int idx = i; idx > 0; idx -= (idx & -idx)) {
      s += bit[p][idx];
    }
    return s;
  }
};
long long int N;
int main() {
  cin >> N;
  Vl arr(N);
  cin >> arr;
  VVl poses(1e6);
  for (long long int i = (0), i_end_ = (N); i < i_end_; ++i) {
    arr[i]--;
    poses[arr[i]].push_back(i + 1);
  }
  long long int ans = 0;
  {
    BinaryIndexedTree tree(N);
    for (long long int k = (0), k_end_ = (1e6); k < k_end_; ++k) {
      for (long long int p : poses[k]) {
        tree.add(p, 1);
        long long int l, r;
        if (tree.sum(p) == 1) {
          l = -1;
        } else {
          l = tree.lower_bound(tree.sum(p) - 1);
        }
        r = tree.lower_bound(tree.sum(p) + 1);
        ans -= (p - l - 1) * (r - p + 1) * k;
      }
    }
  }
  {
    BinaryIndexedTree tree(N);
    for (long long int k = (1e6) - 1, k_begin_ = (0); k >= k_begin_; --k) {
      for (long long int p : poses[k]) {
        tree.add(p, 1);
        long long int l, r;
        if (tree.sum(p) == 1) {
          l = -1;
        } else {
          l = tree.lower_bound(tree.sum(p) - 1);
        }
        r = tree.lower_bound(tree.sum(p) + 1);
        ans += (p - l - 1) * (r - p + 1) * k;
      }
    }
  }
  cout << ans << '\n';
}

```