#ifndef DEBUG
#  define NDEBUG
#endif
#include <iostream>
#include <string>
#include <iterator>
#include <utility>
#include <type_traits>
#include <limits>
#include <cassert>
#include <vector>

using namespace std;

// template {{{
// misc {{{
using Z = long long;
[[maybe_unused]]
constexpr Z INF = numeric_limits<Z>::max() / 3;
// }}}

// debug {{{
template <class T>
using enable_if_sequence_t = enable_if_t<
  is_same<
    typename iterator_traits<
      typename remove_cv_t<remove_reference_t<T>>::iterator
    >::iterator_category,
    random_access_iterator_tag>{}>;
#ifdef NDEBUG
# define dump(x)
# define debug if (0)
template <class T>
inline T&& ix(T&& value) { return value; }
template <class T, class Index, class... Indices, class = enable_if_sequence_t<T>>
inline auto&& ix(T&& container, Index index, Indices... indices) {
  return ix(container[index], indices...);
}
#else
# define dump(x) do { \
    cerr << "\e[33m[dump: " << __LINE__ << "] " << (#x) << " = " << x << "\e[0m" << endl; \
  } while (0);
# define debug
template <class T>
inline auto&& ix_impl([[maybe_unused]] int line, [[maybe_unused]] const char* code, T&& value) {
  return value;
}
template <class T, class Index, class... Indices, class = enable_if_sequence_t<T>>
inline auto&& ix_impl(int line, const char* code, T&& container, Index index, Indices... indices) {
  if (index < 0) {
    cerr << "\e[31mix: negative index at line " << line << ", ix(" << code << ")\e[0m" << endl;
    exit(1);
  }
  int size = container.size();
  if (index >= size) {
    cerr << "\e[31mix: index out of range at line " << line << ", ix(" << code << ")\n"
      << "index = " << index << " whereas size = " << size << "\e[0m" << endl;
    exit(1);
  }
  return ix_impl(line, code, container[index], indices...);
}
#define ix(...) ix_impl(__LINE__, #__VA_ARGS__, __VA_ARGS__)
#endif
// }}}

// IO {{{
template <class T>
false_type is_container_impl(...);
template <class T, class = typename T::iterator>
true_type is_container_impl(T);
template <class T>
struct is_container : decltype(is_container_impl<T>(declval<T>())) {};
template <>
struct is_container <string> : std::false_type {};
template <class Container, class = enable_if_t<is_container<Container>{}>>
istream& operator>> (istream& is, Container& cont) {
  for (auto& v : cont) is >> v;
  return is;
}
template <class Container, class = enable_if_t<is_container<Container>{}>>
ostream& operator<< (ostream& os, Container const& cont) {
  bool first = true;
  constexpr char sep =
    is_container<typename Container::value_type>{} ? '\n' : ' ';
  for (auto const& v : cont) {
    if (!first) {
      os << sep;
    }
    first = false;
    os << v;
  }
  return os;
}
template <class T, class U>
ostream& operator<< (ostream& os, pair<T, U> p) {
  os << '(' << p.first << ", " << p.second << ')';
  return os;
}
// }}}
// }}}

class sparse_table {
  private:
    size_t len;
    vector<vector<Z>> data;
  public:
    sparse_table(vector<Z> const& v): len(v.size()), data(len) {
      for (auto i = 0; i < len; i++)
        data[i].push_back(v[i]);
      for (auto j = 1; (1 << j) <= len; j++) {
        for (auto i = 0; i < len; i++) {
          if (i + (1 << j) > len) break;
          data[i].push_back(max(data[i][j - 1], data[i + (1 << (j - 1))][j - 1]));
        }
      }
      dump(data);
    }
    Z maximum(int left, int right) {
      int width = right - left, w = 0;
      while ((1 << (w + 1)) <= width) w++;
      Z ans = -INF;
      int pos = left;
      for (int i = 0; (1 << i) <= width; i++) {
        int w = 1 << i;
        if (!(w & width)) continue;
        ans = max(ans, data[pos][i]);
        pos += w;
      }
      return ans;
    }
};


template <class T, class F>
T boundary(F is_ok, T ok, T ng) {
  while (abs(ok - ng) > 1) {
    T m = (ok + ng) / 2;
    (is_ok(m) ? ok : ng) = m;
  }
  return ok;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  Z N;
  cin >> N;
  vector<Z> ps(N);
  cin >> ps;
  sparse_table st(ps);
  Z ans = 0;
  for (auto i = 0; i < N; i++) {
    if (ix(ps, i) == N) continue;
    dump(i);
    Z left_small, left_large, right_small, right_large;
    if (st.maximum(0, i) < ix(ps, i)) {
      dump(st.maximum(0, i));
      left_small = i + 1;
      left_large = 0;
    }
    else {
      Z lr = boundary([&] (Z j) { return st.maximum(j, i) > ix(ps, i); }, 0, i);
      dump(lr);
      left_small = i - lr;
      if (st.maximum(0, lr) < ix(ps, i))
        left_large = lr + 1;
      else {
        Z ll = boundary<Z>([&] (Z j) { return st.maximum(j, lr) > ix(ps, i); }, 0, lr);
        dump(ll);
        left_large = lr - ll;
      }
    }
    if (st.maximum(i, N) <= ix(ps, i)) {
      right_small = N - i;
      right_large = 0;
    }
    else {
      Z rl = boundary<Z>([&] (Z j) { return st.maximum(i, j) > ix(ps, i); }, N, i) - 1;
      dump(rl);
      right_small = rl - i;
      if (st.maximum(rl + 1, N) <= ix(ps, i))
        right_large = N - rl;
      else {
        Z rr = boundary([&] (Z j) { return st.maximum(rl + 1, j) > ix(ps, i); }, N, rl + 1) - 1;
        dump(rr);
        right_large = rr - rl;
      }
    }
    ans += ix(ps, i) * (left_small * right_large + left_large * right_small);
    dump(left_small);
    dump(left_large);
    dump(right_small);
    dump(right_large);
  }
  cout << ans << endl;
}


Measured memory_bytes: 22016