Problem:


Score: 500 points

Problem Statement

Given is a permutation P of \{1, 2, \ldots, N\}.

For a pair (L, R) (1 \le L \lt R \le N), let X_{L, R} be the second largest value among P_L, P_{L+1}, \ldots, P_R.

Find \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

Constraints

 2 \le N \le 10^5 

 1 \le P_i \le N 

 P_i \neq P_j  (i \neq j)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N

Output

Print \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

Sample Input 1

3
2 3 1

Sample Output 1

5

X_{1, 2} = 2, X_{1, 3} = 2, and X_{2, 3} = 1, so the sum is 2 + 2 + 1 = 5.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

30

Sample Input 3

8
8 2 7 3 4 5 6 1

Sample Output 3

136



Sample input:
3
2 3 1


Sample output:
5

Submission status: Accepted

Solution code:
n=int(input())
p=list(map(int,input().split()))
# 数字xのあるidxを取得するdict
dn={x:i for i,x in enumerate(p)}

def segfunc(x, y):
    return x+y
ide_ele = 0
class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

st=SegTree([0]*n,segfunc,0)
ans=0
st.update(dn[n],1)
for i in range(n-1,0,-1):
    # 左が0となる最大のidxを検索
    l,r=0,dn[i]
    while r-l>1:
        x=(l+r)//2
        if st.query(x,dn[i]+1)>0:
            l,r=x,r
        else:
            l,r=l,x
    l0=l if st.query(l,dn[i]+1)==0 else r
    # 左が1となる最大のidxを検索。l0=0なら存在しない
    if l0==0:
        l1=-1
    else:
        l,r=0,l0
        while r-l>1:
            x=(l+r)//2
            if st.query(x,dn[i]+1)>1:
                l,r=x,r
            else:
                l,r=l,x
        l1=l if st.query(l,dn[i]+1)==1 else r
    # 右が0となる最小のidxを検索
    l,r=dn[i],n-1
    while r-l>1:
        x=(l+r)//2
        if st.query(dn[i],x+1)>0:
            l,r=l,x
        else:
            l,r=x,r
    r0=r if st.query(dn[i],r+1)==0 else l
    # 右が1となる最小のidxを検索。r0=n-1なら存在しない
    if r0==n-1:
        r1=-1
    else:
        l,r=r0,n-1
        while r-l>1:
            x=(l+r)//2
            if st.query(dn[i],x+1)>1:
                l,r=l,x
            else:
                l,r=x,r
        r1=r if st.query(dn[i],r+1)==1 else l
    if l1!=-1:
        ans+=(l0-l1)*(r0-dn[i]+1)*i
    if r1!=-1:
        ans+=(dn[i]-l0+1)*(r1-r0)*i
    st.update(dn[i],1)
print(ans)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.lch = None
        self.rch = None
        self.bias = 0
 
 
class AVLTree:
    def __init__(self):
        self.root = None
 
    def rotate_left(self, v):
        u = v.rch
        v.rch = u.lch
        u.lch = v
        if u.bias == -1:
            u.bias = v.bias = 0
        else:
            u.bias = 1
            v.bias = -1
        return u
 
    def rotate_right(self, v):
        u = v.lch
        v.lch = u.rch
        u.rch = v
        if u.bias == 1:
            u.bias = v.bias = 0
        else:
            u.bias = -1
            v.bias = 1
        return u
 
    def rotateLR(self, v):
        u = v.lch
        t = u.rch
        u.rch = t.lch
        t.lch = u
        v.lch = t.rch
        t.rch = v
        self.update_bias_double(t)
        return t
 
    def rotateRL(self, v):
        u = v.rch
        t = u.lch
        u.lch = t.rch
        t.rch = u
        v.rch = t.lch
        t.lch = v
        self.update_bias_double(t)
        return t
 
    def update_bias_double(self, v):
        if v.bias == 1:
            v.rch.bias = -1
            v.lch.bias = 0
        elif v.bias == -1:
            v.rch.bias = 0
            v.lch.bias = 1
        else:
            v.rch.bias = 0
            v.lch.bias = 0
        v.bias = 0
 
    def add(self, key):
        if self.root is None:
            self.root = Node(key)
            return
 
        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lch
            elif v.key < key:
                history.append((v, -1))
                v = v.rch
            else:
                return
 
        p, pdir = history[-1]
        if pdir == 1:
            p.lch = Node(key)
        else:
            p.rch = Node(key)
 
        while history:
            v, direction = history.pop()
            v.bias += direction
 
            new_v = None
            b = v.bias
            if b == 0:
                break
 
            if b == 2:
                u = v.lch
                if u.bias == -1:
                    new_v = self.rotateLR(v)
                else:
                    new_v = self.rotate_right(v)
                break
            if b == -2:
                u = v.rch
                if u.bias == 1:
                    new_v = self.rotateRL(v)
                else:
                    new_v = self.rotate_left(v)
                break
 
        if new_v is not None:
            if len(history) == 0:
                self.root = new_v
                return
            p, pdir = history.pop()
            if pdir == 1:
                p.lch = new_v
            else:
                p.rch = new_v
 
    def lower_bound(self, key):
        ret = None
        v = self.root
        while v is not None:
            if v.key >= key:
                if ret is None or ret > v.key:
                    ret = v.key
                v = v.lch
            else:
                v = v.rch
        return ret
 
    def upper_bound(self, key):
        ret = None
        v = self.root
        while v is not None:
            if v.key <= key:
                if ret is None or ret < v.key:
                    ret = v.key
                v = v.rch
            else:
                v = v.lch
        return ret
 
if __name__ == '__main__':
    N = int(input())
    P = [(p, i) for i, p in enumerate(map(int, input().split()))]
    P.sort()
 
    T = AVLTree()
    _, i = P.pop()
    T.add(i)
    T.add(-1)
    T.add(N)
 
    ans = 0
    while P:
        p, i = P.pop()
        l = T.upper_bound(i)
        r = T.lower_bound(i)
        ll = T.upper_bound(l-1)
        if ll is None:
            ll = -1
        rr = T.lower_bound(r+1)
        if rr is None:
            rr = N
        ans += p*((l-ll)*(r-i) + (rr-r)*(i-l))
        T.add(i)
    print(ans)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.lch = None
        self.rch = None
        self.bias = 0
        self.size = 1


class AVLTree:
    def __init__(self):
        self.root = None

    def rotate_left(self, v):
        u = v.rch

        u.size = v.size
        v.size -= u.rch.size + 1 if u.rch is not None else 1

        v.rch = u.lch
        u.lch = v
        if u.bias == -1:
            u.bias = v.bias = 0
        else:
            u.bias = 1
            v.bias = -1
        return u

    def rotate_right(self, v):
        u = v.lch

        u.size = v.size
        v.size -= u.lch.size + 1 if u.lch is not None else 1

        v.lch = u.rch
        u.rch = v
        if u.bias == 1:
            u.bias = v.bias = 0
        else:
            u.bias = -1
            v.bias = 1
        return u

    def rotateLR(self, v):
        u = v.lch
        t = u.rch

        t.size = v.size
        v.size -= u.size - (t.rch.size if t.rch is not None else 0)
        u.size -= t.rch.size + 1 if t.rch is not None else 1

        u.rch = t.lch
        t.lch = u
        v.lch = t.rch
        t.rch = v
        self.update_bias_double(t)
        return t

    def rotateRL(self, v):
        u = v.rch
        t = u.lch

        t.size = v.size
        v.size -= u.size - (t.lch.size if t.lch is not None else 0)
        u.size -= t.lch.size + 1 if t.lch is not None else 1

        u.lch = t.rch
        t.rch = u
        v.rch = t.lch
        t.lch = v
        self.update_bias_double(t)
        return t

    def update_bias_double(self, v):
        if v.bias == 1:
            v.rch.bias = -1
            v.lch.bias = 0
        elif v.bias == -1:
            v.rch.bias = 0
            v.lch.bias = 1
        else:
            v.rch.bias = 0
            v.lch.bias = 0
        v.bias = 0

    def add(self, key):
        if self.root is None:
            self.root = Node(key)
            return

        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lch
            elif v.key < key:
                history.append((v, -1))
                v = v.rch
            else:
                return

        p, pdir = history[-1]
        if pdir == 1:
            p.lch = Node(key)
        else:
            p.rch = Node(key)

        while history:
            v, direction = history.pop()
            v.bias += direction
            v.size += 1

            new_v = None
            b = v.bias
            if b == 0:
                break

            if b == 2:
                u = v.lch
                if u.bias == -1:
                    new_v = self.rotateLR(v)
                else:
                    new_v = self.rotate_right(v)
                break
            if b == -2:
                u = v.rch
                if u.bias == 1:
                    new_v = self.rotateRL(v)
                else:
                    new_v = self.rotate_left(v)
                break

        if new_v is not None:
            if len(history) == 0:
                self.root = new_v
                return
            p, pdir = history.pop()
            p.size += 1
            if pdir == 1:
                p.lch = new_v
            else:
                p.rch = new_v

        while history:
            p, pdir = history.pop()
            p.size += 1

    def remove(self, key):
        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lch
            elif v.key < key:
                history.append((v, -1))
                v = v.rch
            else:
                break
        else:
            return False

        if v.lch is not None:
            history.append((v, 1))
            lmax = v.lch
            while lmax.rch is not None:
                history.append((lmax, -1))
                lmax = lmax.rch

            v.key = lmax.key

            v = lmax

        c = v.rch if v.lch is None else v.lch

        if history:
            p, pdir = history[-1]
            if pdir == 1:
                p.lch = c
            else:
                p.rch = c
        else:
            self.root = c
            return True

        while history:
            new_p = None

            p, pdir = history.pop()
            p.bias -= pdir
            p.size -= 1

            b = p.bias
            if b == 2:
                if p.lch.bias == -1:
                    new_p = self.rotateLR(p)
                else:
                    new_p = self.rotate_right(p)

            elif b == -2:
                if p.rch.bias == 1:
                    new_p = self.rotateRL(p)
                else:
                    new_p = self.rotate_left(p)

            elif b != 0:
                break

            if new_p is not None:
                if len(history) == 0:
                    self.root = new_p
                    return True
                gp, gpdir = history[-1]
                if gpdir == 1:
                    gp.lch = new_p
                else:
                    gp.rch = new_p
                if new_p.bias != 0:
                    break

        while history:
            p, pdir = history.pop()
            p.size -= 1

        return True

    def member(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lch
            elif v.key < key:
                v = v.rch
            else:
                return True
        return False

    def lower_bound(self, key):
        ret = None
        v = self.root
        while v is not None:
            if v.key >= key:
                if ret is None or ret > v.key:
                    ret = v.key
                v = v.lch
            else:
                v = v.rch
        return ret

    def upper_bound(self, key):
        ret = None
        v = self.root
        while v is not None:
            if v.key <= key:
                if ret is None or ret < v.key:
                    ret = v.key
                v = v.rch
            else:
                v = v.lch
        return ret

    def find_kth_element(self, k):
        """0オリジン
        """
        v = self.root
        s = 0
        while v is not None:
            t = s+v.lch.size if v.lch is not None else s
            if t == k:
                return v.key
            elif t < k:
                s = t+1
                v = v.rch
            else:
                v = v.lch
        return None

    def __contains__(self, key): return self.member(key)
    def __delitem__(self, key): return self.remove(key)
    def __bool__(self): return self.root is not None
    def __len__(self): return self.root.size if self.root is not None else 0


if __name__ == '__main__':
    N = int(input())
    P = [(p, i) for i, p in enumerate(map(int, input().split()))]
    P.sort()

    T = AVLTree()
    _, i = P.pop()
    T.add(i)

    ans = 0
    while P:
        p, i = P.pop()
        T.add(i)
        r = T.lower_bound(i+1)
        if r is None:
            r = N
        rr = T.lower_bound(r+1)
        if rr is None:
            rr = N
        l = T.upper_bound(i-1)
        if l is None:
            l = -1
        ll = T.upper_bound(l-1)
        if ll is None:
            ll = -1
        ans += p*((l-ll)*(r-i) + (rr-r)*(i-l))
    print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# 後でよく見る
# 構築は O(1)、挿入・削除・検索は O(log L)

class BalancingTree:
    def __init__(self, n):
        self.N = n
        self.root = self.node(1 << n, 1 << n)

    def debug(self):
        def debug_info(nd_):
            return (nd_.value - 1, nd_.pivot - 1, nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re
        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def append(self, v):# v を追加（その時点で v はない前提）
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                # v がすでに存在する場合に何か処理が必要ならここに書く
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        if nd.left: return self.leftmost(nd.left)
        return nd

    def rightmost(self, nd):
        if nd.right: return self.rightmost(nd.right)
        return nd

    def find_l(self, v): # vより真に小さいやつの中での最大値（なければ-1）
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v): # vより真に大きいやつの中での最小値（なければRoot）
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    if prev == 2**17:
                        return N
                    else:
                        return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    if prev == 2**17:
                        return N
                    else:
                        return prev - 1

    @property
    def max(self):
        return self.find_l((1<<self.N)-1)

    @property
    def min(self):
        return self.find_r(-1)

    def delete(self, v, nd = None, prev = None): # 値がvのノードがあれば削除（なければ何もしない）
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None

N = getN()
P = getList()

A = []
for i in range(N):
    A.append((P[i],i))

A.sort(reverse = True)

# 10 ** 5ならだいたい2 ** 17ぐらい用意
BT = BalancingTree(17)

ans = 0
for i in range(N):
    # xは8, 7... yは8, 7...のインデックス
    x, y = A[i]
    BT.append(y)
    a = BT.find_l(y)
    b = BT.find_l(a)
    c = BT.find_r(y)
    d = BT.find_r(c)
    ans += ((a - b) * (c - y) + (d - c) * (y - a)) * x

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# [Pl, Pr]間で２番目に大きいものの総和を
# l, rについてのnC2通りの全てについて求めよ

# 8 2 7 3 4 5 6 1
# 8 2: 2
# 8 2 7: 7
# 2 7 3: 3
# 8を含むもの（７通り）について2が２番目になるもの、7が２番目になるもの...
# 2を含むものについて（６通り）について7が...をそれぞれO(1)で求められれば

# N <= 10 ** 5
# Piが２番目になる通りが何通り　みたいな感じで求められる？
# Piが２番目になる条件　→　自分より上位のものを一つだけ含む

# ヒープキューとか使える？
# 二つ数字を入れる　→　最小値を取り出せばそれは２番目の数字
# 尺取り使える？

# 累積？　一番

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)
        self.b = 1 << N.bit_length() - 1

    def add(self, a, w):
        x = a
        while(x <= self.N):
            self.bit[x] += w
            x += x & -x

    def get(self, a):
        ret, x = 0, a - 1
        while(x > 0):
            ret += self.bit[x]
            x -= x & -x
        return ret

    def cum(self, l, r):
        return self.get(r) - self.get(l)

    def lowerbound(self,w):
        if w <= 0:
            return 0
        x = 0
        k = self.b
        while k > 0:
            if x + k <= self.N and self.bit[x + k] < w:
                w -= self.bit[x + k]
                x += k
            k //= 2
        return x + 1

N = getN()
P = getList()
dic = {}
bit = BIT(N)
for i in range(N):
    dic[P[i]] = i + 1

# 両端に何もない時用
# [0] + Pの各要素 + [N + 1]みたいになる
dic[0] = 0
dic[N + 1] = N + 1
ans = 0

for i in range(N, 0, -1):
    # 8のインデックス、7のインデックス...に1を登録していく
    bit.add(dic[i], 1)
    # 左側にある既に登録したもの（自分より大きいもの + 自分）の数を数える
    c = bit.get(dic[i] + 1)
    # l1: 左側にある既に登録したもの（自分より大きいもの）のうち、一番右にあるもの
    # l2: l1の一つ左側にあるもの
    l1, l2 = bit.lowerbound(c - 1), bit.lowerbound(c - 2)
    # r1: 右側にある既に登録したもの（自分より大きいもの）のうち、一番左にあるもの
    # r2: r1の一つ右側にあるもの
    r1, r2 = bit.lowerbound(c + 1), bit.lowerbound(c + 2)
    S = (l1 - l2) * (r1 - dic[i]) + (r2 - r1) * (dic[i] - l1)
    ans += S * i
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left
from bisect import bisect_right


class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.elem = [0] * (n + 1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        self.elem[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j=None):
        """ 部分区間和 [i, j) """
        if j is None:
            return self.elem[i]
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, s):
        """ [a0, a1, a2, ...] """
        return self.elem[s]

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for s in self.elem[:self.n]:
            yield s

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

####################################################################################################


class BitSet:

    """ 挿入、削除、k番目の値を取得、全てがO(logN)で可能。重複にも対応。"""
    """ 原理的に ai>=0 であるため、二分探索が可能である点も重要　　　　　"""
    def __init__(self, n, A=[]):
        """
        :param n: Aの要素の最大値
        :param A:
        self.size: BitSetに含まれている要素の個数
        """
        self.n = n
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(x, 1)
        self.size += 1
        self.flip += self.size - self.p.sum(x+1)        # 転倒数を使わないなら消してOK

    def remove(self,x):
        self.p.add(x, -1)
        self.size -= 1

    def order(self,x):
        """
        x が小さい順で何番目かを取得（1-indexed)
        BIT.order(x) = bisect_left(BIT.sort(),x) + 1
        BIT.minimum(BIT.order(x)) = BIT.lower_bound(x) = Aに含まれる x 以上の最小の要素
        """
        return self.p.sum(x) + 1

    def flip_counter(self):
        return self.flip

    def count(self,x):
        return self.p[x]

    def minimum(self,k=1):
        """ k 番目に小さい値を取得 （1-indexed）  """
        if k <= self.size:
            return self.p.lower_bound(k)[0] + 1
        else:
            sys.stderr.write("minimum: list index out of range (k={0})\n".format(k))

    def min(self):
        return self.minimum(1)

    def max(self):
        return self.p.lower_bound(self.size)[0] + 1

    def upper_bound(self,x):
        """ x以下の最大の要素の値を返す """
        k = self.p.sum(x+1)
        if k:
            return self.minimum(k)
        else:
            sys.stderr.write("upper_bound: no element smaller than {0} in this BitSet\n".format(x))

    def lower_bound(self,x):
        """ x以上の最小の要素の値を返す """
        k = self.p.sum(x) + 1
        if k <= self.size:
            return self.minimum(k)
        else:
            sys.stderr.write("lower_bound: no element larger than {0} in this BitSet\n".format(x))

    def __getitem__(self, k):
        """ ソートした時の k 番目の要素 (0-indexed)  """
        if k >= 0:
            return self.minimum(k+1)
        else:
            return self.minimum(self.size + 1 + k)

    def __iter__(self):
        for i in range(self.n+1):
            if self.p[i]:
                for _ in range(self.p[i]):
                    yield i

    def __str__(self):
        text1 = " ".join(list(map(str, self)))
        return "[" + text1 + "]"

####################################################################################################

def max2(x,y):
    return x if x > y else y

def min2(x,y):
    return x if x < y else y


N = int(input())
data = []
for i, p in enumerate(map(int, input().split())):
    data.append((i, p))
data.sort(key=lambda x:x[1])

i, p = data.pop()

BIT = BitSet(N)
BIT.add(i)
res = 0
while data:
    i, p = data.pop()
    x = BIT.order(i)
    R = BIT.minimum(x) if x <= BIT.size else N
    RR = BIT.minimum(x+1) if x+1 <= BIT.size else N
    L = BIT.minimum(x-1) if x-1 >= 1 else -1
    LL = BIT.minimum(x-2) if x-2 >= 1 else -1
    if i < R:
        res += p*(RR - R)*(i - L)
    if i > L:
        res += p*(L - LL)*(R - i)
    BIT.add(i)
print(res)