using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;

namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        //平行二分探索木参考(http://wwwa.pikara.ne.jp/okojisan/avl-tree/index.html)
        class BinarySearchTree<T> where T : IComparable<T>
        {
            class node<T> where T : IComparable<T>
            {
                public node<T> left = null;
                public node<T> right = null;
                public T key = default(T);
                public node<T> parent = null;
                public int height;
            }
            node<T> root = null;
            bool change;
            int height(node<T> t) => t?.height ?? 0;
            int bias(node<T> t) => height(t.left) - height(t.right);
            void modHeight(node<T> t) => t.height = 1 + Math.Max(height(t.left), height(t.right));
            node<T> rotateL(node<T> v)
            {
                var u = v.right;
                var t2 = u.left;
                u.left = v; u.parent = v.parent; v.parent = u;
                if (u.parent != null)
                    if (u.parent.right == v) u.parent.right = u;
                    else u.parent.left = u;
                else
                    root = u;
                v.right = t2; if (t2 != null) t2.parent = v;
                modHeight(u.left);
                modHeight(u);
                return u;
            }
            node<T> rotateR(node<T> u)
            {
                var v = u.left;
                var t2 = v.right;
                v.right = u;v.parent = u.parent;u.parent = v;
                if (v.parent != null)
                    if (v.parent.right == u) v.parent.right = v;
                    else v.parent.left = v;
                else
                    root = v;
                u.left = t2;if (t2 != null) t2.parent = u;
                modHeight(v.right);
                modHeight(v);
                return v;
            }
            node<T> rotateLR(node<T> t)
            {
                t.left = rotateL(t.left);
                return rotateR(t);
            }
            node<T> rotateRL(node<T> t)
            {
                t.right = rotateR(t.right);
                return rotateL(t);
            }
            node<T> balanceLi(node<T> t) => balanceL(t);
            node<T> balanceRi(node<T> t) => balanceR(t);
            node<T> balanceLd(node<T> t) => balanceR(t);
            node<T> balanceRd(node<T> t) => balanceL(t);

            node<T> balanceL(node<T> t)
            {
                if (!change) return t;
                var h = height(t);
                if (bias(t) == 2)
                {
                    if (0 <= bias(t.left))
                        t = rotateR(t);
                    else
                        t = rotateLR(t);
                }
                else modHeight(t);
                change = (h != height(t));
                return t;
            }
            node<T> balanceR(node<T> t)
            {
                if (!change) return t;
                var h = height(t);
                if (bias(t) == -2)
                {
                    if (bias(t.right) <= 0)
                        t = rotateL(t);
                    else
                        t = rotateRL(t);
                }
                else modHeight(t);
                change = (h != height(t));
                return t;
            }


            public BinarySearchTree() { }

            public void insert(T z)
            {
                change = true;
                _insert(new node<T>() { key = z, height = 1 });
            }
            void _insert(node<T> z)
            {
                node<T> y = null;
                node<T> x = root;
                while (x != null)
                {
                    y = x;
                    if (z.key.CompareTo(x.key) < 0)
                        x = x.left;
                    else
                        x = x.right;
                }
                if (y == null)
                {
                    root = z;
                    change = false;
                }
                else if (z.key.CompareTo(y.key) < 0)
                {
                    y.left = z;
                    y.left.parent = y;
                }
                else
                {
                    y.right = z;
                    y.right.parent = y;
                }
                var s = z;
                while (s.parent != null)
                {
                    if (s.parent.left == s)
                        s = balanceLi(s.parent);
                    else
                        s = balanceRi(s.parent);
                }
            }
            public bool find(T v)
            {
                var n = _find(v);
                return n == null ? false : true;
            }
            node<T> _find(T v)
            {
                var x = root;
                while (x != null)
                {
                    if (x.key.CompareTo(v) == 0)
                        return x;
                    if (x.key.CompareTo(v) < 0)
                        x = x.right;
                    else
                        x = x.left;
                }
                return null;
            }

            public void delete(T v) {
                change = true;
                _delete(_find(v));
            }
            void _delete(node<T> n)
            {
                if (n == null)
                    return;
                if (n == root)
                {
                    change = false;
                    if (n.left == null && n.right == null)
                        root = null;
                    else if (n.left != null && n.right == null)
                    {
                        root = n.left;
                        root.parent = null;
                    }
                    else if (n.left == null && n.right != null)
                    {
                        root = n.right;
                        root.parent = null;
                    }
                    else
                    {
                        var next = n.right;
                        while (next.left != null)
                            next = next.left;
                        n.key = next.key;
                        change = true;
                        _delete(next);
                    }
                    return;
                }
                var spl = n.parent.left;
                if (n.left == null && n.right == null)
                {
                    if (n == n.parent.right)
                        n.parent.right = null;
                    else
                        n.parent.left = null;
                }
                else if (n.left != null && n.right == null)
                {
                    n.left.parent = n.parent;
                    if (n == n.parent.right)
                        n.parent.right = n.left;
                    else
                        n.parent.left = n.left;
                }
                else if (n.left == null && n.right != null)
                {
                    n.right.parent = n.parent;
                    if (n == n.parent.right)
                        n.parent.right = n.right;
                    else
                        n.parent.left = n.right;
                }
                else
                {
                    var next = n.right;
                    while (next.left != null)
                        next = next.left;
                    n.key = next.key;
                    _delete(next);
                }
                var s = n;
                while (s.parent != null)
                {
                    if (spl == s)
                        s = balanceLd(s.parent);
                    else
                        s = balanceRd(s.parent);
                    spl = s.parent?.left;
                }
            }

            List<T> preorder;
            public IReadOnlyList<T> PreOrder { get { return preorder.AsReadOnly(); } }
            List<T> inorder;
            public IReadOnlyList<T> InOrder { get { return inorder.AsReadOnly(); } }
            public void order()
            {
                preorder = new List<T>();
                inorder = new List<T>();
                _order(root);
            }
            void _order(node<T> n)
            {
                if (n == null)
                    return;
                preorder.Add(n.key);
                _order(n.left);
                inorder.Add(n.key);
                _order(n.right);
            }
            public bool prev(T v, ref T r)
            {
                var t = _find(v);
                if (null == t)
                    return false;
                if (null != t.left)
                {
                    t = t.left;
                    while (t.right != null)
                        t = t.right;
                    r = t.key;
                    return true;
                }
                while (t.parent != null)
                {
                    if (t.parent.right == t)
                    {
                        r = t.parent.key;
                        return true;
                    }
                    t = t.parent;
                }
                return false;
            }
            public bool next(T v, ref T r)
            {
                var t = _find(v);
                if (null == t)
                    return false;
                if (null != t.right)
                {
                    t = t.right;
                    while (t.left != null)
                        t = t.left;
                    r = t.key;
                    return true;
                }
                while (t.parent != null)
                {
                    if (t.parent.left == t)
                    {
                        r = t.parent.key;
                        return true;
                    }
                    t = t.parent;
                }
                return false;
            }
        }
        static void Main(string[] args)
        {
            var N = Sarray()[0];
            var P = Sarray();
            var bst = new BinarySearchTree<long>();
            var idx = new long[N];
            for (long i = 0; i < N; ++i)
                idx[P[i] - 1] = i;

            long ans = 0L;
            for (var i = N - 1; 0 <= i; --i)
            {
                long ll = -1;
                long l = -1;
                long r = N;
                long rr = N;
                bst.insert(idx[i]);
                bst.prev(idx[i], ref l);
                bst.prev(l, ref ll);
                bst.next(idx[i], ref r);
                bst.next(r, ref rr);
                ans += (i + 1) * ((l - ll) * (r - idx[i]) + (rr - r) * (idx[i] - l));
            }
            WriteLine(ans);
        }
    }
}


Measured memory_bytes: 34780