#include <bits/stdc++.h>
#define loop(n) for (int ngtkana_is_genius = 0; ngtkana_is_genius < int(n); ngtkana_is_genius++)
#define rep(i, begin, end) for(int i = int(begin); i < int(end); i++)
#define all(v) v.begin(), v.end()
#define lint long long
auto cmn = [](auto& a, auto b){if (a > b) {a = b; return true;} return false;};
auto cmx = [](auto& a, auto b){if (a < b) {a = b; return true;} return false;};
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail){
  std::cerr << " " << head;
  debug_impl(tail...);
}
#define debug(...)\
  std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
  debug_impl(__VA_ARGS__);\
  std::cerr << std::noboolalpha;

template <typename T, typename Add, typename Sub>
class binary_indexed_tree
{
public:
  using size_type         = int;
  using value_type        = T;
  using add_function_type = Add;
  using sub_function_type = Sub;
  using container_type    = std::vector<T>;

private:
  size_type         sz;
  size_type         n;
  add_function_type add_function;
  sub_function_type sub_function;
  value_type        id;
  container_type    table;

public:
  binary_indexed_tree
  (
    size_type         size,
    add_function_type add_function,
    sub_function_type sub_function,
    value_type        id,
    container_type    v
  ) :
  sz           (size),
  n            (std::pow(2, int(std::log2(size)) + 1)),
  add_function (std::move(add_function)),
  sub_function (std::move(sub_function)),
  id           (id),
  table        (n, id)
  {}

  binary_indexed_tree(
    size_type         size,
    add_function_type add_function,
    sub_function_type sub_function,
    value_type        id
  ) :
    binary_indexed_tree(
      size,
      std::move(add_function),
      std::move(sub_function),
      id,
      container_type(size, id)
    )
  {}

  auto operator[] (size_type i) const -> value_type
  {
    assert(0 <= i && i < n);
    return query(i, i + 1);
  }

  auto at (size_type i) const -> value_type
  {
    return operator[](i);
  }

  auto collect () {
    std::vector<value_type> ret(sz);
    for (auto i = 0; i < sz; i++) {
      ret.at(i) = at(i);
    }
    return ret;
  }

  // Returns the sum over [0, k[.
  auto cumulative_sum(size_type k) const -> value_type
  {
    static_assert(std::is_same<size_type, int>::value, "");
    assert(0 <= k && k <= n);
    value_type ret = id;
    for (k--; k >= 0; k &= k + 1, k--) {
      ret = add_function(ret, table.at(k));
    };
    return ret;
  }

  // Return the sum over [l, r[.
  auto query (size_type l, size_type r) const -> value_type
  {
    assert(0 <= l && l <= r && r <= n);
    return sub_function(cumulative_sum(r), cumulative_sum(l));
  }


  void add (size_type i, value_type x)
  {
    assert(0 <= i && i < n);
    for (; i < n; i |= i + 1) {
      table.at(i) = add_function(table.at(i), x);
    }
  }

  void update (size_type i, value_type x)
  {
    add(i, sub_function(x, at(i)));
  }
};

template<typename T, typename Add, typename Sub>
auto make_binary_indexed_tree(
  int size,
  Add add_function,
  Sub sub_function,
  T   id
)
{
  return binary_indexed_tree<T, Add, Sub>
  (
    size,
    std::move(add_function),
    std::move(sub_function),
    id
  );
}

template<typename T, typename Add, typename Sub>
auto make_binary_indexed_tree
(
  int            size,
  Add            add_function,
  Sub            sub_function,
  T              id,
  std::vector<T> v
)
{
  return binary_indexed_tree<T, Add, Sub>
  (
    size,
    std::move(add_function),
    std::move(sub_function),
    id,
    std::move(v)
  );
}

template <typename T>
std::istream& operator>> (std::istream& is, std::vector<T>& v) {
  for (auto & x : v) is >> x;
  return is;
}

template <typename T>
std::ostream& operator<< (std::ostream& os, const std::vector<T>& v) {
  auto n = v.size();
  os << "{";
  for (size_t i = 0; i < n; i++)
    {os << (i > 0 ? "," : "") << v.at(i);}
  return os << "}";
}

template <typename T, typename U>
std::ostream& operator<< (std::ostream& os, const std::pair<T, U>& pair){
  return os << "(" << pair.first << "," << pair.second << ")";
}

template <typename T, typename U>
std::istream& operator>> (std::iostream& is, std::pair<T, U>& pair) {
  return is >> pair.first >> pair.second;
}

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int n; std::cin >> n;
  std::vector<std::pair<int, int>> pairs(n);
  rep(x, 0, n) {
    int y; std::cin >> y;
    pairs.at(x) = {y, x};
  }
  std::sort(all(pairs));
  std::reverse(all(pairs));
  auto ret = 0LL;
  auto bit = make_binary_indexed_tree(
    n,
    [](auto x, auto y){ return x + y; },
    [](auto x, auto y){ return x - y; },
    0
  );
  auto find_left = [&] (int r) {
    auto check = [&] (int l) {
      return bit.query(l, r) >= 1;
    };
    auto lwr = -1, upr = r, md = 0;
    while (abs(lwr - upr) > 1) {
      md = (lwr + upr) >> 1;
      if (check(md)) lwr = md;
      else upr = md;
    }
    return lwr;
  };
  auto find_right = [&] (int l) {
    auto check = [&] (int r) {
      return bit.query(l, r) <= 1;
    };
    if (check(n)) return n;
    auto lwr = l, upr = n, md = 0;
    while (abs(lwr - upr) > 1) {
      md = (lwr + upr) >> 1;
      if (check(md)) lwr = md;
      else upr = md;
    }
    return lwr;
  };
  auto calc_left = [&] (int x) {
    auto r = find_left(x);
    auto l = find_left(r);
    return std::make_pair(r - l, x - r);
  };
  auto calc_right = [&] (int x) {
    auto l = find_right(x);
    auto r = find_right(l);
    return std::make_pair(l - x, r - l);
  };
  for (auto pair : pairs) {
    int y, x; std::tie(y, x) = pair;
    bit.add(x, 1);
    // debug(bit.collect());
    int p, q, r, s;
    std::tie(p, q) = calc_left(x);
    std::tie(r, s) = calc_right(x);
    // debug(y, p, q, r, s);
    ret += (lint)y * (p * r + q * s);
  }
  std::cout << ret << std::endl;
  return 0;
}

Measured memory_bytes: 1920