#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
#include<boost/operators.hpp>
#include<boost/dynamic_bitset.hpp>

namespace adaptor = boost::adaptors;
using index_t = std::size_t;

template<class T, class Op = std::plus<>>class seg_tree
{
	std::vector<T> vec;
	T unit;
	std::size_t sz;
	Op op;
	static std::size_t get_size(std::size_t s)
	{
		std::size_t ret = 1;
		while (ret < s)
		{
			ret <<= 1;
		}
		return ret;
	}
public:
	seg_tree(std::size_t size, T u = T(), Op f = Op()) :vec(), unit(u), sz(get_size(size)), op(f)
	{
		vec.assign(2 * sz, unit);
	}
	template<class Range>void set(Range const& rng)
	{
		std::size_t i = 0;
		for (auto&& v : rng)
		{
			vec[i + sz] = v;
			if (++i >= sz)
			{
				break;
			}
		}
		for (auto s = sz / 2; s > 0; s /= 2)
		{
			for (auto i : boost::irange<std::size_t>(0, s))
			{
				vec[(i + s)] = op(vec[2 * (i + s)], vec[2 * (i + s) + 1]);
			}
		}
	}
	T operator()(std::size_t start, std::size_t end)const
	{
		T L = unit, R = unit;
		for (std::size_t a = start + sz, b = end + sz; a < b; a >>= 1, b >>= 1)
		{
			if (a & 1)
			{
				L = op(L, vec[a++]);
			}
			if (b & 1)
			{
				R = op(vec[--b], R);
			}
		}
		return op(L, R);
	}
	void update(std::size_t i, T const& v)
	{
		auto k = i + sz;
		vec[k] = v;
		while (k >>= 1)
		{
			vec[k] = op(vec[2 * k], vec[2 * k + 1]);
		}
	}
};
struct max_t
{
	template<class T>T const& operator()(T const& lhs, T const& rhs)const
	{
		return std::max(lhs, rhs);
	}
};

class memoization_t
{
	std::vector<int> index;
	seg_tree<int, max_t> tree;
	std::set<std::pair<int, int>> flag;
	std::int64_t run(int L, int R, int v)
	{
		if (R - L <= 1)
		{
			return 0;
		}
		else if (flag.count(std::make_pair(L, R)))
		{
			return 0;
		}
		flag.emplace(L, R);
		auto i = index[v];
		std::int64_t ret = 0;
		std::int64_t lc = 0, rc = 0;
		int lmax = -1, rmax = -1;
		if (i == L)
		{
			rmax = tree(L + 1, R);
			rc = std::int64_t(R - index[rmax]);
			ret += (rmax + 1) * rc;
			ret += run(L, index[rmax], v);
			ret += run(L + 1, R, rmax);
		}
		else if (i == R - 1)
		{
			lmax = tree(L, R - 1);
			lc = std::int64_t(index[lmax] - L + 1);
			ret += (lmax + 1) * lc;
			ret += run(index[lmax] + 1, R, v);
			ret += run(L, R - 1, lmax);
		}
		else
		{
			lmax = tree(L, i);
			rmax = tree(i + 1, R);
			if (lmax < rmax)
			{
				rc = std::int64_t(i - L + 1) * std::int64_t(R - index[rmax]);
				ret += (rmax + 1) * rc;
				ret += run(L, index[rmax], v);
				ret += run(i + 1, R, rmax);
			}
			else
			{
				lc = std::int64_t(index[lmax] - L + 1) * std::int64_t(R - i);
				ret += (lmax + 1) * lc;
				ret += run(L, i, lmax);
				ret += run(index[lmax] + 1, R, v);
			}
		}
		return ret;
	}
public:
	memoization_t(std::vector<int> _index, seg_tree<int, max_t> _tree) :
		index(std::move(_index)),
		tree(std::move(_tree)),
		flag()
	{

	}
	memoization_t(memoization_t const&) = delete;
	memoization_t(memoization_t&&) = delete;

	auto operator()()
	{
		auto ret = run(0, index.size(), index.size() - 1);
		return ret;
	}
};


void Main()
{
	int N;
	std::cin >> N;
	std::vector<int> index(N);
	seg_tree<int, max_t> tree(N);
	for (auto i : boost::irange(0, N))
	{
		int v;
		std::cin >> v;
		--v;
		index[v] = i;
		tree.update(i, v);
	}
	memoization_t func(std::move(index), std::move(tree));
	std::cout << func() << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

Measured memory_bytes: 15488