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: Wrong Answer

Solution code:
# Treap
#平衡二分木　乱数を用いてできるだけ平衡を保つらしい　
#priorityには乱数を入れること
# d = 0: right rotation
# d = 1: left rotation
def rotate(nd, d):
    c = nd[d]
    if d:
        e = c[1]
        nd[1] = c[0]
        c[0] = nd
    else:
        e = c[0]
        nd[0] = c[1]
        c[1] = nd

    r = c[4] = nd[4]
    nd[4] = r - (e[4] if e else 0) - 1
    return c

root = None
def insert(val, pri):
    global root
    st = []
    dr = []
    x = root
    while x:
        st.append(x)
        if x[2] == val:
            return
        d = (x[2] < val)
        dr.append(d)
        x = x[d]

    # [<left>, <right>, <key>, <priority>, <count>]
    nd = [None, None, val, pri, 1]
    while st:
        x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] += 1
        if x[3] >= nd[3]:
            break
        rotate(x, d)
    else:
        root = nd

    for x in st:
        x[4] += 1

def __delete(nd):
    st = []; dr = []
    while nd[0] or nd[1]:
        l = nd[0]; r = nd[1]
        d = (l[3] <= r[3]) if l and r else (l is None)
        st.append(rotate(nd, d))
        dr.append(d ^ 1)
    nd = x = None
    while st:
        nd = x; x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] -= 1
    return x

def delete(val):
    global root
    x = root

    st = []
    y = None
    while x:
        if val == x[2]:
            break
        y = x; d = (x[2] < val)
        st.append(y)
        x = x[d]
    else:
        return

    if y:
        y[d] = __delete(x)
        for x in st:
            x[4] -= 1
    else:
        root = __delete(x)

def find(val):
    global root
    x = root
    while x:
        if val == x[2]:
            return 1
        x = x[x[2] < val]
    return 0

def search1(val):
    global root
    x = root
    ans=-1
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            ans=max(ans,x[2])
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans

def search2(val):
    global root
    x=root
    ans=10**20
    while x:
        if val==x[2]:
            return val
        if val>x[2]:
            if x[1]==None:
                return ans
            else:
                x=x[1]
        if val<x[2]:
            ans=min(ans,x[2])
            if x[0]==None:
                return ans
            else:
                x=x[0]
    return ans

import random

N=int(input())
P=list(map(int,input().split()))
dic={key:-1 for key in range(1,N+1)}
for i in range(0,N):
    dic[P[i]]=i

answer=0
for i in range(0,N):
    k=N-i
    l1=search1(dic[k])
    l2=search1(l1-1)
    r1=search2(dic[k])
    r2=search2(r1+1)
    if r2!=10**20:
        if l2!=-1:
            answer+=k*(dic[k]-l1)*(r2-r1)+k*(l1-l2)*(r1-dic[k])
        elif l1!=-1:
            answer+=k*(dic[k]-l1)*(r2-r1)+k*(r1-dic[k])*(l1+1)
        else:
            answer+=k*(dic[k]+1)*(r2-r1)
    else:
        if r1!=10**20:
            if l2!=-1:
                answer+=k*(N-r1)*(dic[k]-l1)+k*(r1-dic[k])*(l1-l2)
            elif l1!=-1:
                answer+=k*(N-r1)*(dic[k]-l1)+k*(N-dic[k])*(l1+1)
            else:
                answer+=k*(N-r1)*(dic[k]+1)
        else:
            if l2!=-1:
                answer+=k*(N-dic[k])*(l1-l2)
            elif l1!=-1:
                answer+=k*(N-dic[k])*(l1+1)
    insert(dic[k],random.randint(1,100000))

print(answer)

Submission status: Wrong Answer

Solution code:
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n=int(input())
p=list(map(int,input().split()))
d=[0]*n
for i in range(n):d[p[i]-1]=i
bit=BinaryIndexedTree(n)
def lower_bound_bit(m):
  left=-1
  right=n
  while left+1!=right:
    mid=(left+right)//2
    if bit.sum(0,mid)>=m:right=mid
    else:left=mid
  return right
ans=0
for i in range(n-1,-1,-1):
  if i==n-1:
    bit.add(d[i],1)
    continue
  m=bit.sum(0,d[i])
  if bit.sum(0,n-1)!=m:
    r=lower_bound_bit(m+2)-lower_bound_bit(m+1)
    l=d[i]-lower_bound_bit(m)
    if 0==m:l+=1
    ans+=(i+1)*l*r
    #print("r",i+1,l,r)
  if 0!=m:
    r=lower_bound_bit(m+1)-d[i]
    l=lower_bound_bit(m)-lower_bound_bit(m-1)
    if bit.sum(0,0)==m:l=1
    ans+=(i+1)*l*r
    #print("l",i+1,l,r)
  bit.add(d[i],1)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect


class SqrtSet:
    def __init__(self, block_limit=201):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit

    def search_lower(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_left(self.key, key)
        if i != 0:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect.bisect_left(block, key)
        if i != 0:
            ret = block[i - 1]
        return ret
        
    def search_higher(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_right(self.key, key)
        if i != len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect.bisect_right(block, key)
        if i != len(block):
            ret = block[i]
        return ret

    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.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 dump(self):
        for b in self.child:
            print(len(b), end=" ")
        print("")
            
            
def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: -p[i])
    t = SqrtSet()
    t.insert(-10)
    t.insert(n+10)
    ans = 0
    for i in range(n):
        if i==0:
            t.insert(idx[i])
            continue
        ri = t.search_higher(idx[i])
        pri = t.search_higher(ri)
        if pri==None:
            pri=n
            ri=n
        if pri==n+10:
            pri=n
        le = t.search_lower(idx[i])
        ple=t.search_lower(le)
        if ple==None:
            if le==-10:
                le=-1
                ple=-1
        if ple==-10:
            ple=-1
        #print(ple,le,idx[i],ri,pri)
        ans+=(n-i)*((le-ple)*(ri-idx[i])+(pri-ri)*(idx[i]-le))
        #print(n-i,ans)
        t.insert(idx[i])
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

class Node:
    def __init__(self, key, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ
        self.lmax = None #左部分木のキーの最大値

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key): self.root = self.insert_sub(self.root, key)
    
    def insert_sub(self, t, key): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key)
            return self.balanceR(t)
        else:
            self.change = False
            return t

    ###############
    #Nodeの探索
    ###############

    def lower_bound(self, key, leastValue):
        t = self.root
        bound = leastValue
        while t:
            if key <= t.key: t = t.left
            else:
                bound = t.key
                t = t.right
        return bound 

    def upper_bound(self, key, largestValue):
        t = self.root
        bound = largestValue
        while t:
            if key < t.key:
                bound = t.key
                t = t.left
            else: t = t.right
        return bound

def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = dict() 
    for i, p in enumerate(P): pindex[p - 1] = i
    Ans = 0
    T = AVLTree()
    T.insert(pindex[N-1])
    for i in reversed(range(N-1)):
        pid = pindex[i]
        #left, right = T.lower_bound(pid, -1), T.upper_bound(pid, N)
        #l2, r2 = T.lower_bound(left, -1), T.upper_bound(right, N)
        #Ans += (i + 1) * ((pid - left) * (r2 - right) + (right - pid) * (left - l2))
        T.insert(pid)
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys

class Node:
    def __init__(self, key, value, height):
        self.key = key #ノードの木
        self.height = height #このノードを根とする部分木の高さ
        self.value = value #ノードの値
        self.left = None
        self.right = None

    def size(self, n): return 0 if n is None else n.height

    def bias(self): #左の方が高いと正、右が高いと負の値を返す
        return self.size(self.left) - self.size(self.right)

    #木の高さの計算
    def calcSize(self):
        self.height = 1 + max(self.size(self.left), self.size(self.right))

class AVLTree:
    def __init__(self):
        self.root = None #根
        self.change = False #修正フラグ
        self.lmax = None #左部分木のキーの最大値
        self.value = None #lmaxの値

    ###############
    #回転操作, 修正操作
    ###############
    def rotateL(self, n): #ノードnの左回転
        r = n.right; rl = r.left
        r.left = n; n.right = rl
        r.left.calcSize()
        r.calcSize()
        return r

    def rotateR(self, n):
        l = n.left; lr = l.right
        l.right = n; n.left = lr
        l.right.calcSize()
        l.calcSize()
        return l

    def rotateLR(self, n): #二重回転;左回転→右回転
        n.left = self.rotateL(n.left)
        return self.rotateR(n)

    def rotateRL(self, n):
        n.right = self.rotateR(n.right)
        return self.rotateL(n)
        
    def balanceL(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == 2:
            if n.left.bias() >= 0: n = self.rotateR(n)
            else: n = self.rotateLR(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    def balanceR(self, n):
        if not self.change: return n
        h = n.height
        if n.bias() == -2:
            if n.right.bias() <= 0: n = self.rotateL(n)
            else: n = self.rotateRL(n)
        else: n.calcSize()
        self.change = (h != n.height)
        return n

    ###############
    #Nodeの追加
    ###############
    def insert(self, key, value): self.root = self.insert_sub(self.root, key, value)
    
    def insert_sub(self, t, key, value): #新たなノードの挿入。初期位置は根。
        if t is None:
            self.change = True
            return Node(key, value, 1)
        if key < t.key:
            t.left = self.insert_sub(t.left, key, value)
            return self.balanceL(t)
        elif key > t.key:
            t.right = self.insert_sub(t.right, key, value)
            return self.balanceR(t)
        else:
            self.change = False
            t.value = value
            return t

    ###############
    #Nodeの削除
    ###############
    def delete(self, key): self.root = self.delete_sub(self.root, key)

    def delete_sub(self, t, key):
        if t is None:
            self.change = False
            return None
        if key < t.key:
            t.left = self.delete_sub(t.left, key)
            return self.balanceR(t)
        elif key > t.key:
            t.right - self.delete_sub(t.right, key)
            return self.balanceL(t)
        else:
            if t.left is None:
                self.change = True
                return t.right
            else:
                t.left = self.delete_max(t.left)
                t.key = self.lmax
                t.value = self.value
                return self.balanceR(t)
    
    def delete_max(self, n):
        if n.right is None: #nの右部分木が存在しない場合は左部分木を昇格させる
            self.change = True
            self.lmax = n.key
            self.value = n.value
            return n.left
        else:
            n.right = self.delete_max(n.right)
            return self.balanceL(n)

    ###############
    #Nodeの探索
    ###############
    def search(self, key):
        t = self.root
        while t:
            if key < t.key: t = t.left
            elif key > t.key: t = t.right
            else: return True
        return False

    def getValue(self, key):
        t = self.root
        while t:
            if key < t.key: t = t.left
            elif key > t.key: t = t.right
            else: return t.value
        return None

    def lower_bound(self, key, leastValue):
        t = self.root
        bound = leastValue
        while t:
            if key <= t.key: t = t.left
            else:
                bound = t.key
                t = t.right
        return bound 

    def upper_bound(self, key, largestValue):
        t = self.root
        bound = largestValue
        while t:
            if key < t.key:
                bound = t.key
                t = t.left
            else: t = t.right
        return bound

def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    pindex = [0] * N
    for i, p in enumerate(P): pindex[p - 1] = i
    Ans = 0
    T = AVLTree()
    T.insert(pindex[N-1], N)
    for i in reversed(range(N-1)):
        pid = pindex[i]
        left, right = T.lower_bound(pid, -1), T.upper_bound(pid, N)
        l2, r2 = T.lower_bound(left, -1), T.upper_bound(right, N)
        if left == -1: Ans += (i + 1) * (r2 - right) * (pid + 1)
        elif right == N: Ans += (i + 1) * (left - l2) * (N - pid)
        else: Ans += (i + 1) * ((pid - left) * (r2 - right) + (N - pid) * (left - l2))
        T.insert(pid, i+1)
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
# Cumulative Sum Bisect


class SegTree():
    def __init__(self, N, e=0, operator_func=lambda x,y:x+y):
        self.e = e

        self.N = N
        bitlen = (N).bit_length()
        self.size = 2**(bitlen if N&(N-1) else bitlen-1)
        self.node = [self.e] * (2*self.size)
        self.op = operator_func

    def set_list(self, l):
        for i,j in enumerate(l):
            self.node[i+self.size-1] = j
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x

    def bisect_left(self, x):
        if x > self.node[0]:
            return self.N
        p, ans = 0, 0
        node_size = 2 * self.size - 1
        x -= 1

        while p < node_size:
            ans = p - (self.size - 1)
            p1, p2 = 2 * p + 1, 2 * p + 2

            if p1 < node_size and self.node[p1] <= x:
                x -= self.node[p1]
                p = p2
            else:
                p = p1
        
        return ans+1


if __name__ == "__main__":
    # ABC140-E sample
    N = int(input())
    l = [(j, i) for i, j in enumerate(map(int, input().split()))]
    l.sort(key=lambda x:-x[0])
    tree = SegTree(N)
 
    ans = 0
 
    for n, (value, idx) in enumerate(l, start=1):
        v = tree.get(0, idx + 1)
        a = tree.bisect_left(v - 1) if v > 1 else 0
        b = tree.bisect_left(v - 0) if v else 0
        c = tree.bisect_left(v + 1) if n-v>1 else N+1
        d = tree.bisect_left(v + 2) if n-v>2 else N+1
        print(v, a, b, c, d)
 
        tree.update(idx, 1)
        idx += 1
        ans += ((b-a)*(c-idx)+(d-c)*(idx-b)) * value
 
    print(ans)

Submission status: Wrong Answer

Solution code:
# Cumulative Sum Bisect


class SegTree():
    def __init__(self, N, e=0, operator_func=lambda x,y:x+y):
        self.e = e

        self.N = N
        bitlen = (N).bit_length()
        self.size = 2**(bitlen if N&(N-1) else bitlen-1)
        self.node = [self.e] * (2*self.size - 1)
        self.op = operator_func

    def set_list(self, l):
        for i,j in enumerate(l):
            self.node[i+self.size-1] = j
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x

    def bisect_left(self, x):
        if x > self.node[0]:
            return self.N
        p, ans = 0, 0
        node_size = 2 * self.size - 1
        x -= 1

        while p < node_size:
            ans = p - (self.size - 1)
            p1, p2 = 2 * p + 1, 2 * p + 2

            if p1 < node_size and self.node[p1] <= x:
                x -= self.node[p1]
                p = p2
            else:
                p = p1
        
        return ans


if __name__ == "__main__":
    # ABC140-E sample
    N = int(input())
    l = [(j, i) for i, j in enumerate(map(int, input().split()))]
    l.sort(key=lambda x:-x[0])
    tree = SegTree(N)
 
    ans = 0
 
    for n, (value, idx) in enumerate(l, start=1):
        v = tree.get(0, idx + 1)
        a = tree.bisect_left(v - 1)+1 if v > 1 else 0
        b = tree.bisect_left(v - 0)+1 if v else 0
        c = tree.bisect_left(v + 1)+1 if n-v>1 else N+1
        d = tree.bisect_left(v + 2)+1 if n-v>2 else N+1
 
        tree.update(idx, 1)
        idx += 1
        ans += ((b-a)*(c-idx)+(d-c)*(idx-b)) * value
 
    print(ans)

Submission status: Wrong Answer

Solution code:
#incited from https://juppy.hatenablog.com/entry/2019/02/26/python_AVL%E6%9C%A8_%E9%85%8D%E5%88%97ver_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder_
#AVL-Tree code by juppy

#AVL

##search(0,x):O(logN)
# xがある場合indexを、ない場合Noneを返す
def search(root,key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            return None
        else:
            return search(avl_left[root],key)
    if avl_key[root] < key:
        if avl_right[root] == None:
            return None
        else:
            return search(avl_right[root],key)
    return root


##end_lower/higher:search_lower/higherで使用
def end_lower(root):
    if avl_left[root] == None:
        return avl_key[root]
    else:
        return end_lower(avl_left[root])

def end_higher(root):
    if avl_right[root] == None:
        return avl_key[root]
    else:
        return end_higher(avl_right[root])


##search_lower(0,x,None):O(logN)
# xより小さいものの中で最も大きいものを出力。ない場合はNoneを出力
def search_lower(root,key,lower_key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            return lower_key
        else:
            return search_lower(avl_left[root],key,lower_key)
    if avl_key[root] < key:
        lower_key = avl_key[root]
        if avl_right[root] == None:
            return lower_key
        else:
            return search_lower(avl_right[root],key,lower_key)
    
    # == 
    if avl_left[root] == None:
        return lower_key
    else:
        if lower_key == None:
            return end_higher(avl_left[root])
        else:
            return max(lower_key,end_higher(avl_left[root]))

##search_higher(0,x,None):O(logN)
# xより大きいものの中で最も小さいものを出力。ない場合はNoneを出力
def search_higher(root,key,higher_key):
    if avl_key[root] > key:
        higher_key = avl_key[root]
        if avl_left[root] == None:
            return higher_key
        else:
            return search_higher(avl_left[root],key,higher_key)
    if avl_key[root] < key:
        if avl_right[root] == None:
            return higher_key
        else:
            return search_higher(avl_right[root],key,higher_key)
    
    # == 
    if avl_right[root] == None:
        return higher_key
    else:
        if higher_key == None:
            return end_lower(avl_right[root])
        else:
            return min(higher_key,end_lower(avl_right[root]))



##Rotation,replace,insertx:insertで使用
def DoubleRightRotation(x):
    tl = avl_left[x]
    avl_left[x] = avl_right[avl_right[tl]]
    avl_right[avl_right[tl]] = x
    tlr = avl_right[tl]
    avl_right[tl] = avl_left[tlr]
    avl_left[tlr] = tl
    if balance[tlr] == -1:
        balance[avl_right[tlr]] = 1
        balance[avl_left[tlr]] = 0
    elif balance[tlr] == 1:
        balance[avl_right[tlr]] = 0
        balance[avl_left[tlr]] = -1
    else:
        balance[avl_right[tlr]] = 0
        balance[avl_left[tlr]] = 0
    balance[tlr] = 0
    return tlr

def DoubleLeftRotation(x):
    tr = avl_right[x]
    avl_right[x] = avl_left[avl_left[tr]]
    avl_left[avl_left[tr]] = x
    trl = avl_left[tr]
    avl_left[tr] = avl_right[trl]
    avl_right[trl] = tr
    if balance[trl] == 1:
        balance[avl_right[trl]] = 0
        balance[avl_left[trl]] = -1
    elif balance[trl] == -1:
        balance[avl_left[trl]] = 0
        balance[avl_right[trl]] = 1
    else:
        balance[avl_right[trl]] = 0
        balance[avl_left[trl]] = 0
    balance[trl] = 0
    return trl

def SingleLeftRotation(x):
    tr = avl_right[x]
    balance[tr] = 0
    balance[x] = 0
    avl_right[x] = avl_left[tr]
    avl_left[tr] = x
    return tr

def SingleRightRotation(x):
    tl = avl_left[x]
    balance[tl] = 0
    balance[x] = 0
    avl_left[x] = avl_right[tl]
    avl_right[tl] = x
    return tl

def replace(x,p,v):
    if avl_left[p] == x:
        avl_left[p] = v
    else:
        avl_right[p] = v

def insertx(root,p,key):
    if avl_key[root] > key:
        if avl_left[root] == None:
            avl_key.append(key)
            avl_left[root] = len(avl_key)-1
        else:
            if not insertx(avl_left[root],root,key):
                return False
        if balance[root] == 1:
            balance[root] = 0
            return False
        elif balance[root] == 0:
            balance[root] = -1
            return True
        else:
            if balance[avl_left[root]] == 1:
                replace(root,p,DoubleRightRotation(root))
            elif balance[avl_left[root]] == -1:
                replace(root,p,SingleRightRotation(root))
            return False
    if avl_key[root] < key:
        if avl_right[root] == None:
            avl_key.append(key)
            avl_right[root] = len(avl_key)-1
        else:
            if not insertx(avl_right[root],root,key):
                return False
        if balance[root] == -1:
            balance[root] = 0
            return False
        elif balance[root] == 0:
            balance[root] = 1
            return True
        else:
            if balance[avl_right[root]] == -1:
                replace(root,p,DoubleLeftRotation(root))
            elif balance[avl_right[root]] == 1:
                replace(root,p,SingleLeftRotation(root))
            return False
    return False


##insert(0,x):O(logN)
#x追加
def insert(root,key):
    if key < avl_key[root]:
        if avl_left[root] == None:
            avl_key.append(key)
            avl_left[root] = len(avl_key)-1
        else:
            insertx(avl_left[root],root,key)
    elif key > avl_key[root]:
        if avl_right[root] == None:
            avl_key.append(key)
            avl_right[root] = len(avl_key)-1
        else:
            insertx(avl_right[root],root,key)
    else:
        pass

n=int(input())
arr=list(map(int,input().split()))
arr2=[[arr[i],i+1] for i in range(n)]
arr2=sorted(arr2,reverse=True,key=lambda x:x[0])
avl_key=[0]
avl_left=[None]*n
avl_right=[None]*n
balance=[0]*n
ans=0
for i in range(n):
  val,pos=arr2[i]
  fl=search_lower(0,pos,0)
  if fl!=0:
    sl=search_lower(0,fl,-1)
    if sl==-1:
      sl=0
  else:
    sl=0
  fr=search_higher(0,pos,n+1)
  if fr!=n+1:
    sr=search_higher(0,fr,-1)
    if sr==-1:
      sr=n+1
  else:
    sr=n+1
  cnt=(fl-sl)*(fr-pos)+(pos-fl)*(sr-fr)
  ans+=cnt*val
  insert(0,pos)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N=int(input())
    n=N+2
    def init_max(init_max_val):
        #set_val
        for i in range(n):
            seg_max[i+num_max-1]=init_max_val[i]
        for i in range(num_max-2,-1,-1) :
            seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
        
    def update_max(k,x):
        k += num_max-1
        seg_max[k] = x
        while k:
            k = (k-1)//2
            seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
        
    def query_max(p,q):
        if q<=p:
            return ide_ele_max
        p += num_max-1
        q += num_max-2
        res=ide_ele_max
        while q-p>1:
            if p&1 == 0:
                res = max(res,seg_max[p])
            if q&1 == 1:
                res = max(res,seg_max[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = max(res,seg_max[p])
        else:
            res = max(max(res,seg_max[p]),seg_max[q])
        return res
    ide_ele_max = 0
    num_max =2**(n-1).bit_length()
    seg_max=[ide_ele_max]*2*num_max

    def init_min(init_min_val):
        #set_val
        for i in range(n):
            seg_min[i+num_min-1]=init_min_val[i]    
        #built
        for i in range(num_min-2,-1,-1) :
            seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2]) 
        
    def update_min(k,x):
        k += num_min-1
        seg_min[k] = x
        while k:
            k = (k-1)//2
            seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])
        
    def query_min(p,q):
        if q<=p:
            return ide_ele_min
        p += num_min-1
        q += num_min-2
        res=ide_ele_min
        while q-p>1:
            if p&1 == 0:
                res = min(res,seg_min[p])
            if q&1 == 1:
                res = min(res,seg_min[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = min(res,seg_min[p])
        else:
            res = min(min(res,seg_min[p]),seg_min[q])
        return res
    ide_ele_min = n-1
    num_min =2**(n-1).bit_length()
    seg_min=[ide_ele_min]*2*num_min

    init_max([0]*n)
    init_min([N+1]*n)
    p=list(map(int,input().split()))
    indexes=[0]*N #pの大きいものから順に何番目にあるか
    for idx,i in enumerate(p):
        indexes[N-i]=idx
    ans=0
    point=N
    for i in indexes:
        i+=1
        l=query_max(0,i-1)
        ll= 0 if l==0 else query_max(0,l-1)
        r=query_min(i+1,n-1)
        rr= N+1 if r==N+1 else query_min(r+1,n-1)
        ans+=((0 if l==0 else r-i)*(l-ll)+(0 if r==N+1 else i-l)*(rr-r))*point
        point-=1
        update_max(i,i)
        update_min(i,i)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
class BIT:
  
  def __init__(self, N):
    self.n = N
    self.tree = [0]*(self.n+1)
    
  def bsum(self, i):
    s = 0
    while i:
      s += self.tree[i]
      i -= i&(-i)
    return s
  
  def badd(self, i, x):
    while i<=self.n:
      self.tree[i] += x
      i += i&(-i)
  
  def bsearch(self, x):
    i = 0
    step = 1<<(self.n.bit_length()-1)
    while step:
      if i+step<=self.n and self.tree[i+step]<x:
        i += step
      step >>= 1
    return i+1

      
N = int(input())
P = [0]+[int(c) for c in input().split()]

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

bit = BIT(N)

ans = 0
for m in range(N, 0, -1):
  I = ntoi[m]
  L = bit.bsum(I)
  bit.badd(I,1)
  R = N-L-m
  a = bit.bsearch(L-1) if L>1 else 0
  b = bit.bsearch(L) if L>0 else 0
  c = bit.bsearch(L+2) if R>0 else N+1
  d = bit.bsearch(L+3) if R>1 else N+1
  coef = 0
  if b!=0:
    coef += (b-a)*(c-I)
  if c!=0:
    coef += (I-b)*(d-c)
  ans += m*coef

print(ans)