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

Solution (Python):

import sys
N=input()


bit=[ 0 for i in range(N+1) ]
bit[0]=None

def add(x,w):
	while x<=N:
		bit[x]+=w
		x+=x&(-1*x)

def bitsum(x):
	s=0
	while 0<x:
		s+=bit[x]
		x-=x&(-1)*x
	return s

def search(wa):
	if wa<=0: return 0
	if bitsum(N)<wa: return N+1
	r=N
	l=0
	while r-l!=1:
		m=(l+r)/2
		if bitsum(m)<wa:
			l=m
		else:
			r=m	
	return r



A=map(int, sys.stdin.readline().split())

B=[ 0 for i in range(N+1) ]
for i,a in enumerate(A):
	B[a]=i+1

ans=0
x=N
add(B[x],1)

for x in range(N-1,0,-1):
	cur_p=B[x]	
	cur_v=bitsum(cur_p)
	l1=search(cur_v)
	l2=search(cur_v-1)
	r1=search(cur_v+1)
	r2=search(cur_v+2)
	
	
	ans+=( (l1-l2)*(r1-cur_p)+(cur_p-l1)*(r2-r1) )*x
	add(B[x],1)

print ans

Solution (Python):
N = int(input())
P_id = [0]*(N + 1) 
for index, p in enumerate(map(int, input().split())):
    P_id[p] = index

left_next_index = list(range(- 1, N - 1)) + ['うんこ', - 1] 
right_next_index = list(range(1, N + 1)) + [N, 'うんこ']

res = 0
for p in range(1, N):
    l1 = left_next_index[P_id[p]]
    l2 = left_next_index[l1]
    r1 = right_next_index[P_id[p]]
    r2 = right_next_index[r1]
    
    res += p*((l1 - l2)*(r1 - P_id[p]) + (P_id[p] - l1)*(r2 - r1))
    
    left_next_index[r1] = l1
    right_next_index[l1] = r1
    
print(res)

Solution (Python):
import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Solution (Python):

class BinaryIndexedTree:
    def __init__(self, size):
        size = 1 << (size-1).bit_length()
        self.data = [0] * (size+1)
        self.size = size
    
    def add(self, i, w):
        i += 1
        while i <= self.size:
            self.data[i] += w
            i += i & -i

    def sum(self, i):
        """
        [0,i)
        """
        result = 0
        while i > 0:
            result += self.data[i]
            i -= i & -i
        return result

    __getitem__ = sum

    def lower_bound(self, v):
        """
        return smallest i such that v < sum(data[:i])
        """

        s,pos = 0,0
        N = self.size
        k = N
        while k > 0:
            i = pos+k
            if i <= N:
                x = s+self.data[i]
                if x < v:
                    s = x
                    pos = i
            k >>= 1
        return pos


def naive(P):
    def it():
        for i in range(len(P)-1):
            for j in range(i+1,len(P)):
                yield sorted(P[i:j+1])[-2]
    return sum(it())

def solve(P):

    def it():
        bit = BinaryIndexedTree(len(P))
        for cnt, (v,i) in enumerate(sorted(((v,i) for i,v in enumerate(P)), reverse=True)):
            bit.add(i,1)
            c = bit.sum(i)
            
            low1 = -1 if c <= 0 else bit.lower_bound(c)
            low2 = -1 if c <= 1 else bit.lower_bound(c-1)
            up1 = len(P) if c > cnt-1 else bit.lower_bound(c+2)
            up2 = len(P) if c > cnt-2 else bit.lower_bound(c+3)
            yield v*((up1-i)*(low1-low2)+(i-low1)*(up2-up1))
    return sum(it())


if __name__ == '__main__':
    N = int(input())
    P = list(map(int,input().split()))
    print(solve(P))

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
p = LI()
f = [0]*(n+1)
for i in range(n):
    f[p[i]] = i+1

ans = 0
l = [0] + [i for i in range(n+1)]
r = [i + 1 for i in range(n+1)] + [n+1]


for i in range(1,n+1):
    
    x = f[i]
    
    
    
    l1,r1 = l[x],r[x]
    
    
    l2,r2 = l[l1],r[r1]
    
    ans += ((l1-l2)*(r1-x) + (x-l1)*(r2-r1))*i
    
    
    l[r1],r[l1] = l1,r1
print(ans)

Solution (Python):
class Node:
  def __init__(self, v):
    self.v = v
    self.p = None
    self.n = None
  
  def delete(self):
    if self.p:
      self.p.n = self.n
    if self.n:
      self.n.p = self.p

N = int(input())
pp = list(map(int, input().split()))
nn = dict()
prev = None
for i, p in enumerate(pp):
  n = Node(i)
  if prev:
    prev.n = n
    n.p = prev
  nn[p] = n
  prev = n
s = 0
for x in range(1, N):
  c = nn[x]
  ci = c.v
  pi = c.p.v if c.p else -1
  ni = c.n.v if c.n else N
  if c.p:
    ppi = c.p.p.v if c.p.p else -1
    s += x * (pi - ppi) * (ni - ci)
  if c.n:
    nni = c.n.n.v if c.n.n else N
    s += x * (ci - pi) * (nni - ni)
  c.delete()
print(s)

Solution (Python):
class Node:
  def __init__(self, v):
    self.v = v
    self.p = None
    self.n = None
  
  def delete(self):
    if self.p:
      self.p.n = self.n
    if self.n:
      self.n.p = self.p

N = int(input())
pp = list(map(int, input().split()))
nn = dict()
prev = None
for i, p in enumerate(pp):
  n = Node(i)
  if prev:
    prev.n = n
    n.p = prev
  nn[p] = n
  prev = n
s = 0
for x in range(1, N):
  c = nn[x]
  ci = c.v
  pi = c.p.v if c.p else -1
  ni = c.n.v if c.n else N
  if c.p:
    ppi = c.p.p.v if c.p.p else -1
    s += x * (pi - ppi) * (ni - ci)
  if c.n:
    nni = c.n.n.v if c.n.n else N
    s += x * (ci - pi) * (nni - ni)
  c.delete()
print(s)

Solution (Python):
N = int(input())
P = list(map(int, input().split()))
 
index_lst = [0] * N
for index, i in enumerate(P):
    index_lst[i - 1] = index
 
left_next_Index = list(range(-1, N - 1)) + [-1, -1]
right_next_Index = list(range(1, N + 1)) + [N, N]
ans = 0
for i in range(1, N):
    index = index_lst[i - 1]
    
    l1 = left_next_Index[index]
    l2 = left_next_Index[l1]
    r1 = right_next_Index[index]
    r2 = right_next_Index[r1]
    
    ans += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 -l2))
 
    left_next_Index[r1] = l1
    right_next_Index[l1] = r1
 
print (ans)

Solution (Python):
from bisect import bisect_left
import array

n = int(input())
p = []

for i, x in enumerate(map(int, input().split())):
    p.append([x, i])

p.sort(reverse=True)

s = array.array('i', [-1, -1, p[0][1], n, n])



ans = 0
i = 2
for a, x in p[1:]:
    t = bisect_left(s, x)
    ans += a * ((x - s[t-1]) * (s[t+1] - s[t]) + (s[t] - x) * (s[t-1] - s[t-2]))
    
    s.insert(t, x)
    i += 1


print(ans)

Solution (Python):
N = int(input())
P = [int(i) for i in input().split()]

ind = [0]*(N+1)
for i in range(N):
    ind[P[i]] = i+1

ans = 0
l = [0] + [f for f in range(N+1)]
r = [f + 1 for f in range((N+1))] + [N+1]

for j in range(1,N+1):
    f = ind[j]

    l1 = l[f]
    l2 = l[l1]
    r1 = r[f]
    r2 = r[r1]
    ans += ((l1-l2)*(r1-f) + (f-l1)*(r2-r1))*j

    l[r1] = l1
    r[l1] = r1

print(ans)

Solution (Python):
N = int(input())
P = [None] + list(map(int, input().split()))

p_to_index = [None] * (N + 1)
for index, x in enumerate(P[1:], 1):
    p_to_index[x] = index





def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i & (-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i & (-i)
    return s

def BIT_search(x):
    i = 0
    s = 0
    step = 1 << (N.bit_length() - 1)
    while step:
        if i + step <= N and s + tree[i + step] < x:
            i += step
            s += tree[i]
        step >>= 1
    return i + 1

tree = [0] * (N + 1)
ans = 0
for x in range(N, 0, -1):
    c = p_to_index[x]
    L = BIT_sum(c) 
    BIT_add(c)
    R = N - x - L 
    a = BIT_search(L - 1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L + 2) if R >= 1 else N + 1
    e = BIT_search(L + 3) if R >= 2 else N + 1
    tmp = 0
    if b != 0:
        tmp += (b - a) * (d - c)
    if d != 0:
        tmp += (e - d) * (c - b)
    ans += tmp * x

print (ans)

Solution (Python):
N = int(input())
P = list(map(int, input().split()))

index_lst = [0] * N
for index, i in enumerate(P):
    index_lst[i - 1] = index

left_next_Index = list(range(-1, N - 1)) + [-1, -1]
right_next_Index = list(range(1, N + 1)) + [N, N]


ans = 0
for i in range(1, N):
    index = index_lst[i - 1]
    
    l1 = left_next_Index[index]
    l2 = left_next_Index[l1]
    r1 = right_next_Index[index]
    r2 = right_next_Index[r1]
    
    ans += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 -l2))

    left_next_Index[r1] = l1
    right_next_Index[l1] = r1

print (ans)

Solution (Python):

class SegTree:

    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n = int(input())
xs = list(map(int, input().split()))
x2i = {}
for i, x in enumerate(xs):
    x2i[x] = i
ss1 = SegTree([n] * n, n, n, min)
ss2 = SegTree([-1] * n, n, -1, max)

r = 0
for x in range(n):
    x = n - x
    rmi2 = ss1.query(x2i[x]+1, n)
    if rmi2 != n:
        ss1.update(rmi2, n)
    rmi = ss1.query(x2i[x]+1, n)
    if rmi2 != n:
        ss1.update(rmi2, rmi2)

    lmi = ss2.query(0, x2i[x])
    if lmi != -1:
        ss2.update(lmi, -1)
    lmi2 = ss2.query(0, x2i[x])
    if lmi != -1:
        ss2.update(lmi, lmi)
    a,b,c,d =(x2i[x] - lmi), (lmi - lmi2), (rmi - rmi2), (rmi2 - x2i[x])
    r += (a*c + b*d) * x


    ss1.update(x2i[x], x2i[x])
    ss2.update(x2i[x], x2i[x])
print(r)

Solution (Python):
n = int(input())
xs = list(map(int, input().split()))
x2i = {}
for i, x in enumerate(xs):
    x2i[x] = i+1
ll = [0] * (n+2)
rr = [n+1] * (n+2)

def find_l(l, r, default):
    m, m2 = 0, 0
    mi=mi2=default
    for i in range(r-l):
        i = i + l
        if ll[i] > m:
            mi, m = i, ll[i]
    for i in range(r-l):
        i = i + l
        if i == mi:
            continue
        if ll[i] > m2:
            mi2, m2 = i, ll[i]
    return max(mi, mi2), min(mi, mi2)

def find_r(l, r, default):
    m, m2 = n+1, n+1
    mi=mi2=default
    for i in range(r-l):
        i = i + l
        if rr[i] < m:
            mi, m = i, rr[i]
    for i in range(r-l):
        i = i + l
        if i == mi:
            continue
        if rr[i] < m2:
            mi2, m2 = i, rr[i]
    return max(mi, mi2), min(mi, mi2)

class ss_min:

    def __init__(self, init_val, n, ide_ele):
        self.segfunc = min
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
class ss_max:

    def __init__(self, init_val, n, ide_ele):
        self.segfunc = max
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

ssmm = ss_min(rr, n+2, n+1)
ssmm2 = ss_max(ll, n+2, 0)

r = 0
for x in range(n):
    x = n - x


    rmi2 = ssmm.query(x2i[x]+1, n+1)
    ssmm.update(rmi2, n+1)
    rmi = ssmm.query(x2i[x]+1, n+1)
    ssmm.update(rmi2, rmi2)

    lmi = ssmm2.query(0, x2i[x])
    ssmm2.update(lmi, 0)
    lmi2 = ssmm2.query(0, x2i[x])
    ssmm2.update(lmi, lmi)

    a,b,c,d =(x2i[x] - lmi), (lmi - lmi2), (rmi - rmi2), (rmi2 - x2i[x])
    r += (a*c + b*d) * x


    ll[x2i[x]] = x2i[x]
    ssmm.update(x2i[x], x2i[x])
    ssmm2.update(x2i[x], x2i[x])
print(r)

Solution (Python):


import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, P):
    revp = [-1] * (N + 1)
    for i, p in enumerate(P):
        revp[p] = i

    segt = [[(v, 0) for v in P]]
    while len(segt[-1]) > 1:
        base = segt[-1]
        if len(base) % 2 == 1:
            base.append((0, 0))
        new = []
        for i in range(len(base) // 2):
            a, b = base[2 * i]
            c, d = base[2 * i + 1]

            arr = [a, b, c, d]
            arr.sort()
            new.append((arr[-1], arr[-2]))
        segt.append(new)

    dprint('segt', segt)

    def get12(i, j):
        if j - i <= 0:
            return (0, 0)

        segi = 0
        top = []

        while True:
            if j - i <= 0:
                break

            seg = segt[segi]

            if j - i == 1:
                top.extend(seg[i])
                break

            if i % 2 == 1:
                top.extend(seg[i])
                i += 1
            if j % 2 == 1:
                top.extend(seg[j - 1])
                j -= 1

            i //= 2
            j //= 2
            segi += 1

        top.sort()
        return top[-1], top[-2]

    cache = dict()

    stk = [(0, N)]
    while stk:
        item = stk.pop()
        if len(item) == 2:
            i, j = item
            if (i, j) in cache:
                continue

            a, b = get12(i, j)
            ai = revp[a]
            bi = revp[b]
            li, ri = (ai, bi) if ai < bi else (bi, ai)
            ri += 1

            sc = b * (li - i + 1) * (j - ri + 1)

            want = [(i, ri - 1), (li + 1, j), (li + 1, ri - 1)]
            req = []
            for c, d in want:
                if not (d - c < 2 or (c, d) in cache):
                    req.append((c, d))
            if not req:
                left, right, mid = [0 if d - c < 2 else cache[(c, d)]
                                    for c, d in want]
                cache[(i, j)] = left + right - mid + sc
                continue

            stk.append((i, j, want, sc))
            for r in req:
                stk.append(r)
            continue

        i, j, want, sc = item
        left, right, mid = [0 if d - c < 2 else cache[(c, d)]
                            for c, d in want]
        cache[(i, j)] = left + right - mid + sc

    return cache[(0, N)]


def main():
    N = int(inp())
    P = [int(e) for e in inp().split()]
    print(solve(N, P))


if __name__ == '__main__':
    main()

Solution (Python):


import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, P):
    revp = [-1] * (N + 1)
    for i, p in enumerate(P):
        revp[p] = i

    segt = [[(v, 0) for v in P]]
    while len(segt[-1]) > 1:
        base = segt[-1]
        if len(base) % 2 == 1:
            base.append((0, 0))
        new = []
        for i in range(len(base) // 2):
            a, b = base[2 * i]
            c, d = base[2 * i + 1]

            arr = [a, b, c, d]
            arr.sort()
            new.append((arr[-1], arr[-2]))
        segt.append(new)

    dprint('segt', segt)

    def get12(i, j):
        if j - i <= 0:
            return (0, 0)

        segi = 0
        top = []

        while True:
            if j - i <= 0:
                break

            seg = segt[segi]

            if j - i == 1:
                top.extend(seg[i])
                break

            if i % 2 == 1:
                top.extend(seg[i])
                i += 1
            if j % 2 == 1:
                top.extend(seg[j - 1])
                j -= 1

            i //= 2
            j //= 2
            segi += 1

        top.sort()
        return top[-1], top[-2]

    cache = [dict() for _ in range(N)]

    stk = [(0, N)]
    while stk:
        item = stk.pop()
        if len(item) == 2:
            i, j = item
            if j in cache[i]:
                continue

            a, b = get12(i, j)
            ai = revp[a]
            bi = revp[b]
            li, ri = (ai, bi) if ai < bi else (bi, ai)
            ri += 1

            sc = b * (li - i + 1) * (j - ri + 1)

            want = [(i, ri - 1), (li + 1, j), (li + 1, ri - 1)]
            req = []
            for c, d in want:
                if not (d - c < 2 or d in cache[c]):
                    req.append((c, d))
            if not req:
                left, right, mid = [0 if d - c < 2 else cache[c][d]
                                    for c, d in want]
                cache[i][j] = left + right - mid + sc
                continue

            stk.append((i, j, want, sc))
            for r in req:
                stk.append(r)
            continue

        i, j, want, sc = item
        left, right, mid = [0 if d - c < 2 else cache[c][d]
                            for c, d in want]
        cache[i][j] = left + right - mid + sc

    return cache[0][N]


def main():
    N = int(inp())
    P = [int(e) for e in inp().split()]
    print(solve(N, P))


if __name__ == '__main__':
    main()

Solution (Python):


import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, P):
    revp = [-1] * (N + 1)
    for i, p in enumerate(P):
        revp[p] = i

    segt = [[(v, 0) for v in P]]
    while len(segt[-1]) > 1:
        base = segt[-1]
        if len(base) % 2 == 1:
            base.append((0, 0))
        new = []
        for i in range(len(base) // 2):
            a, b = base[2 * i]
            c, d = base[2 * i + 1]

            arr = [a, b, c, d]
            arr.sort()
            new.append((arr[-1], arr[-2]))
        segt.append(new)

    dprint('segt', segt)

    def get12(i, j):
        if j - i <= 0:
            return (0, 0)

        segi = 0
        top = []

        while True:
            if j - i <= 0:
                break

            seg = segt[segi]

            if j - i == 1:
                top.extend(seg[i])
                break

            if i % 2 == 1:
                top.extend(seg[i])
                i += 1
            if j % 2 == 1:
                top.extend(seg[j - 1])
                j -= 1

            i //= 2
            j //= 2
            segi += 1

        top.sort()
        return top[-1], top[-2]

    cache = [dict() for _ in range(N)]

    stk = [(0, N)]
    while stk:
        item = stk.pop()
        if len(item) == 2:
            i, j = item
            if j in cache[i]:
                continue

            a, b = get12(i, j)
            ai = revp[a]
            bi = revp[b]
            li, ri = (ai, bi) if ai < bi else (bi, ai)
            ri += 1

            sc = b * (li - i + 1) * (j - ri + 1)

            want = [(i, ri - 1), (li + 1, j), (li + 1, ri - 1)]
            req = []
            for c, d in want:
                if not (d - c < 2 or d in cache[c]):
                    req.append((c, d))
            if not req:
                left, right, mid = [0 if d - c < 2 else cache[c][d]
                                    for c, d in want]
                cache[i][j] = left + right - mid + sc
                continue

            stk.append((i, j, want, sc))
            for r in req:
                stk.append(r)
            continue

        i, j, want, sc = item
        left, right, mid = [0 if d - c < 2 else cache[c][d]
                            for c, d in want]
        cache[i][j] = left + right - mid + sc

    return cache[0][N]


def main():
    N = int(inp())
    P = [int(e) for e in inp().split()]
    print(solve(N, P))


if __name__ == '__main__':
    main()

Solution (Python):
class BinaryIndexedTree():
    def __init__(self, N):
        self.N = N
        self.arr = [0] * (N+1)

    def query(self, i):
        ret = 0
        i += 1
        while i:
            ret += self.arr[i]
            lsb = i & (-i)
            i -= lsb
        return ret

    def add(self, i, v):
        i += 1
        while i < self.N+1:
            lsb = i & (-i)
            self.arr[i] += v
            i += lsb

    def search(self, x):
        lo = -1
        hi = self.N
        while lo < hi:
            mid = (lo+hi)//2
            if self.query(mid) < x:
                lo = mid + 1
            else:
                hi = mid
        return lo


def main():
    N = int(input())
    P = list(map(int, input().split()))
    idx = [0] * N
    bit = BinaryIndexedTree(N)
    for i in range(N):
        idx[P[i]-1] = i
    ans = 0
    for i in range(N)[::-1]:
        bit.add(idx[i], 1)
        x = bit.query(idx[i])
        l = bit.search(x-1)
        ll = bit.search(x-2)
        r = bit.search(x+1)
        rr = bit.search(x+2)
        tmp = (idx[i]-l) * (rr-r) + (r-idx[i]) * (l-ll)
        ans += (i+1) * tmp
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Solution (Python):
N = int(input())
P = [None] + [int(x) for x in input().split()]
id_list = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    id_list[x] = i



class BIT:
    def __init__(self, n):
        
        self.size = n
        self.tree = [0] * (n + 1) 

    def add(self, i, x=1):
        
        while i <= self.size:
            self.tree[i] += x
            i += i&(-i) 

    def sum(self, i):
        
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i) 
        return s

    def search(self, x):
        
        i = 0
        s = 0
        step = 1<<(N.bit_length()-1) 
        while step:
            if i+step <= N and s + self.tree[i+step] < x:
                i += step
                s += self.tree[i]
            step >>= 1
        return i+1


def main():
    bit = BIT(N)
    ans = 0
    for x in range(N,0,-1):
        idx = id_list[x]
        L = bit.sum(idx) 
        bit.add(idx)
        R = N-x-L 
        ll = bit.search(L-1) if L >= 2 else 0
        l = bit.search(L) if L >= 1 else 0
        r = bit.search(L+2) if R >= 1 else N+1
        rr = bit.search(L+3) if R >= 2 else N+1
        coef = 0
        if l != 0:
            
            coef += (l - ll) * (r - idx)
        if r != 0:
            
            coef += (rr - r) * (idx - l)
        ans += x * coef
    print(ans)

main()

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
ts=time.time()
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False


class Bit:
    def __init__(self,n):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        
    def __str__(self):
        return str(self.arr)
        
    def add(self,i,x):
        k=0
        while i<=self.size:
            k+=1
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1

        
class Bit0(Bit):
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)

n=I()
a=LI()
p=[i+1 for i,j in sorted(enumerate(a),key=lambda x:x[1])]
bt=Bit0(n+2)
bt.add(0,1)
bt.add(n+1,1)
ans=0
for i in range(n-1,-1,-1):
    c=bt.sum(p[i])
    w,x,y,z=[bt.l_bound(c-1+i) for i in range(4)]
    c=p[i]
    bt.add(p[i],1)
    d=(i+1)*((x-w)*(y-c)+(c-x)*(z-y))
    ans+=d
print(ans)

Solution (Python):
N = int(input())
P = map(int, input().split())

pos = {}
for i, p in enumerate(P):
    pos[p] = i+1

foll = [i+1 for i in range(N+1)]+[N+1]
prev = [0]+[i for i in range(N+1)]

ans = 0
for i in range(1, N+1):
    curr = pos[i]
    r = foll[curr]
    rr = foll[r]
    l = prev[curr]
    ll = prev[l]
    ans += (l-ll)*(r-curr)*i
    ans += (rr-r)*(curr-l)*i

    foll[l] = foll[curr]
    prev[r] = prev[curr]
    
    
print(ans)

Solution (Python):
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Solution (Python):
N=int(input())
P=list(map(int,input().split()))
I=[0]*N
for i,p in enumerate(P):
    I[N-p]=i
class BIT:
    def __init__(self,size):
        self.N=size
        self.v=[0]*(self.N+1)
    def add(self,i,x):
        i+=1
        while i<=self.N:
            self.v[i]+=x
            i+=i&-i
    def sum(self,a,b=0):
        if a>b:
            a,b=b,a
        if a>0:
            r=self.sum(b)-self.sum(a)
        else:
            r=0
            i=b
            while i>0:
                r+=self.v[i]
                i-=i&-i
        return r
    def right(self,x):
        a,b=x+1,self.N
        while a+1<b:
            t=(a+b)//2
            if self.sum(a,t)>0:
                b=t
            else:
                a=t
        return a 
    def left(self,x):
        a,b=0,x
        while a+1<b:
            t=(a+b)//2
            if self.sum(t,b)>0:
                a=t
            else:
                b=t
        return a
b=BIT(2**17)
b.add(0,N+1)
b.add(1,N+1)
b.add(N+2,N+1)
b.add(N+3,N+1)
a=0
p=N
for i in I:
    l=b.left(i+2)
    ll=b.left(l)
    r=b.right(i+2)
    rr=b.right(r)
    if 1<l and r<N+2:
        a+=((l-ll)*(r-i-2)+(rr-r)*(i+2-l))*p
    elif 1<l:
        a+=(l-ll)*(N-i)*p
    elif r<N+2:
        a+=(rr-r)*(i+1)*p
    b.add(i+2,p)
    p-=1
print(a)

Solution (Python):
from bisect import*
class SqrtSet:
    def __init__(self,block_limit=201):
        self.key=[]
        self.child=[[]]
        self.block_limit=block_limit
    def le(self,key):
        ret=key
        i=bisect_left(self.key,key)
        if i:ret=self.key[i-1]
        block=self.child[i]
        i=bisect_left(block,key)
        if i:ret=block[i-1]
        return ret
    def ge(self,key):
        ret=key
        i=bisect(self.key,key)
        if i<len(self.key):ret=self.key[i]
        block=self.child[i]
        i=bisect(block,key)
        if i<len(block):ret=block[i]
        return ret
    def insert(self,key):
        i=bisect(self.key,key)
        block=self.child[i]
        insort(block,key)
        if len(block)==self.block_limit:
            sep=self.block_limit//2
            self.key.insert(i,block[sep])
            self.child.insert(i+1,block[sep+1:])
            self.child[i]=block[:sep]
def main():
    n,*p=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(p,1):l[v-1]=i
    t=SqrtSet()
    insert,le,ge=t.insert,t.le,t.ge
    insert(0),insert(n+1)
    a=0
    for i,v in list(enumerate(l,1))[::-1]:
        f,b=ge(v),le(v)
        g,c=ge(f),le(b)
        a+=i*((f-v)*(b-c)+(v-b)*(g-f))
        insert(v)
    print(a)
main()