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):
N = int(input())
P = list(map(int,input().split()))

order = [None] * N
for i,p in enumerate(P):
    order[p-1] = i

bit = [0] * (N+2)
def bit_add(x,w):
    while x <= N+1:
        bit[x] += w
        x += (x & -x)
def bit_sum(x):
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= (x & -x)
    return ret

def bisect_right(k):
    def is_ok(i):
        if i < 1: return True
        if i > N+1: return False
        return bit_sum(i) <= k
    ok = 0
    ng = N+2
    while ng-ok > 1:
        m = (ok+ng) // 2
        if is_ok(m):
            ok = m
        else:
            ng = m
    return ok

ans = 0
for q,i in enumerate(reversed(order)):
    bit_add(i+2, 1)
    
    k = bit_sum(i+2)
    a = bisect_right(k-3)
    b = bisect_right(k-2)
    c = bisect_right(k-1)
    d = bisect_right(k)
    e = bisect_right(k+1)
    ans += ((b-a)*(d-c) + (c-b)*(e-d)) * (N-q)
print(ans)

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

D = [0]*N

for i in range(N):
    D[P[i]-1] = i

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)
        self.N0 = 1
        while self.N0*2 <= self.N:
            self.N0 *= 2

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret

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

bit = BIT([0]*N)

def calc_num(x,l1,l2,h1,h2):
    A = (l1-l2)*(h1-x)
    B = (h2-h1)*(x-l1)
    return A+B

ans = 0

for i in range(N):
    j = N-i-1
    bit.add(D[j],1)
    s = bit.sum(D[j])
    if s==i+1:
        h1=h2=N
    elif s==i:
        h2=N
        h1 = bit.lower_bound(s+1)
    else:
        h1 = bit.lower_bound(s+1)
        h2 = bit.lower_bound(s+2)
    if s==1:
        l1=l2=-1
    elif s==2:
        l1 = bit.lower_bound(s-1)
        l2 = -1
    else:
        l1 = bit.lower_bound(s-1)
        l2 = bit.lower_bound(s-2)

    
    
    ans += calc_num(D[j],l1,l2,h1,h2)*(j+1)

print(ans)