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: Time Limit Exceeded

Solution code:
#root.search(x): ◯.data == x のものが存在するある場合それを出力、ない場合Noneを出力
#root.insert(x): ◯.data == xが存在する場合Falseを出力、ない場合◯.data == x なる頂点を作る
#y.to_s(): 頂点yのdataを出力
#y.left_s(): 頂点yのleftを出力(ない場合はNone)
#root.search_lower(x,None): ○.dataがxより小さいものの中で最も大きいものを出力、ない場合Noneを出力
#root.search_higher(x,None): xより大きいものの中で最も小さいものを出力、ない場合Noneを出力

################################################################################
class Avltree:
    def __init__(self,key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"
    def search(self,key):
        if self.key == None:
            return None
        if self.key > key:
            if self.left == None:
                return None
            else:
                return self.left.search(key)
        if self.key < key:
            if self.right == None:
                return None
            else:
                return self.right.search(key)
        return self # self.key == keyの場合

    def search_lower(self,key,key_lower):
        if self.key == None:
            return key_lower
        if self.key > key:
            if self.left == None:
                return key_lower
            else:
                return self.left.search_lower(key,key_lower)
        if self.key < key:
            key_lower = self.key
            if self.right == None:
                return key_lower
            else:
                return self.right.search_lower(key,key_lower)
        #self.key == keyの場合
        if self.left == None:
            return key_lower
        else:
            if key_lower == None:
                return self.left.end_higher(self.left.key)
            else:
                return max(key_lower,self.left.end_higher(self.left.key))

    def search_higher(self,key,key_higher):
        if self.key == None:
            return key_higher
        if self.key > key:
            key_higher = self.key
            if self.left == None:
                return key_higher
            else:
                return self.left.search_higher(key,key_higher)
        if self.key < key:
            if self.right == None:
                return key_higher
            else:
                return self.right.search_higher(key,key_higher)
        #self.key == keyの場合
        if self.right == None:
            return key_higher
        else:
            if key_higher == None:
                return self.right.end_lower(self.right.key)
            else:
                return min(key_higher,self.right.end_lower(self.right.key))


    def end_lower(self,end_lower_key):
        if self.left == None:
            return end_lower_key
        else:
            end_lower_key = self.left.key
            return self.left.end_lower(end_lower_key)
    def end_higher(self,end_higher_key):
        if self.right == None:
            return end_higher_key
        else:
            end_higher_key = self.right.key
            return self.right.end_higher(end_higher_key)


    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self,p,v): # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else :
            p.right = v
    def insert(self,key): # rootでのみ呼ばれる挿入
        if self.key == None: # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self,key)
        elif key > self.key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self,key)
        else: # key == self.key:
            pass # do not overwrite
    def insertx(self,p,key): # replaceを呼ぶために一つ上の親を持っているinsert
        if self.key > key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                if not self.left.insertx(self, key): # 左の木が生長しなければ、
                    return False # 成長しない
            if self.balance == "Right":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Left"
                return True # 成長した
            elif self.balance == "Left":
                if self.left.balance == "Right":
                    self.replace(p,self.DoubleRightRotation())
                elif self.left.balance == "Left":
                    self.replace(p,self.SingleRightRotation())
                return False # rotationを行うと成長しない
        if self.key < key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                if not self.right.insertx(self, key):
                    return False
            if self.balance == "Left":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Right"
                return True
            elif self.balance == "Right":
                if self.right.balance == "Left":
                    self.replace(p,self.DoubleLeftRotation())
                elif self.right.balance == "Right":
                    self.replace(p,self.SingleLeftRotation())
                return False
        return False # self.key == keyの時は何もしないので成長もしない

    def to_s(self):
        return self.key
    def left_s(self):
        if self.left == None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right == None:
            return None
        return (self.right).key

################################################################
n = int(input())
p = list(map(int,input().split()))
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
ans = 0
avl = Avltree()
avl.insert(q[n])
for i in range(n-1,0,-1):
    cnt = 0
    v = q[i]
    lo = avl.search_lower(v,None)
    hi = avl.search_higher(v,None)
    #print(lo,hi)
    if lo:
        lo2 = avl.search_lower(lo,0)
        t = lo-lo2
        if hi:
            t *= hi - v
        else:
            t *= n+1 - v
        cnt += t
    if hi:
        hi2 = avl.search_higher(hi,n+1)
        t = hi2 - hi
        if lo:
            t *= v - lo
        else:
            t *= v
        cnt += t
    #print(cnt)
    ans += i*cnt
    avl.insert(v)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int,input().split()))
count = 0
for i in range(0,n-1):
  for j in range(i+1,n):
    new = p[i:j+1]
    new.remove(max(new))
    count += max(new)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n = I()
    p = LI()
    r = 0
    a = [-1, n]
    t = sorted(range(n), key=lambda x: -p[x])
    for c in t:
        i = bisect.bisect_left(a,c)
        b = a[i-1]
        d = a[i]
        if d < n:
            r += (c-b) * (a[i+1]-d) * p[c]
        if b >= 0:
            r += (b-a[i-2]) * (d-c) * p[c]
        # print(i,r,'bd',b,d,a,c,p[c])
        bisect.insort_left(a,c)

    return r


print(main())

Submission status: Time Limit Exceeded

Solution code:
#root.search(x): ◯.data == x のものが存在するある場合それを出力、ない場合Noneを出力
#root.insert(x): ◯.data == xが存在する場合Falseを出力、ない場合◯.data == x なる頂点を作る
#y.to_s(): 頂点yのdataを出力
#y.left_s(): 頂点yのleftを出力(ない場合はNone)
#root.search_lower(x,None): ○.dataがxより小さいものの中で最も大きいものを出力、ない場合Noneを出力
#root.search_higher(x,None): xより大きいものの中で最も小さいものを出力、ない場合Noneを出力

################################################################################
class Avltree:
    def __init__(self,key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"
    def search(self,key):
        if self.key == None:
            return None
        if self.key > key:
            if self.left == None:
                return None
            else:
                return self.left.search(key)
        if self.key < key:
            if self.right == None:
                return None
            else:
                return self.right.search(key)
        return self # self.key == keyの場合

    def search_lower(self,key,key_lower):
        if self.key == None:
            return key_lower
        if self.key > key:
            if self.left == None:
                return key_lower
            else:
                return self.left.search_lower(key,key_lower)
        if self.key < key:
            key_lower = self.key
            if self.right == None:
                return key_lower
            else:
                return self.right.search_lower(key,key_lower)
        #self.key == keyの場合
        if self.left == None:
            return key_lower
        else:
            if key_lower == None:
                return self.left.end_higher(self.left.key)
            else:
                return max(key_lower,self.left.end_higher(self.left.key))

    def search_higher(self,key,key_higher):
        if self.key == None:
            return key_higher
        if self.key > key:
            key_higher = self.key
            if self.left == None:
                return key_higher
            else:
                return self.left.search_higher(key,key_higher)
        if self.key < key:
            if self.right == None:
                return key_higher
            else:
                return self.right.search_higher(key,key_higher)
        #self.key == keyの場合
        if self.right == None:
            return key_higher
        else:
            if key_higher == None:
                return self.right.end_lower(self.right.key)
            else:
                return min(key_higher,self.right.end_lower(self.right.key))


    def end_lower(self,end_lower_key):
        if self.left == None:
            return end_lower_key
        else:
            end_lower_key = self.left.key
            return self.left.end_lower(end_lower_key)
    def end_higher(self,end_higher_key):
        if self.right == None:
            return end_higher_key
        else:
            end_higher_key = self.right.key
            return self.right.end_higher(end_higher_key)


    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self,p,v): # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else :
            p.right = v
    def insert(self,key): # rootでのみ呼ばれる挿入
        if self.key == None: # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self,key)
        elif key > self.key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self,key)
        else: # key == self.key:
            pass # do not overwrite
    def insertx(self,p,key): # replaceを呼ぶために一つ上の親を持っているinsert
        if self.key > key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                if not self.left.insertx(self, key): # 左の木が生長しなければ、
                    return False # 成長しない
            if self.balance == "Right":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Left"
                return True # 成長した
            elif self.balance == "Left":
                if self.left.balance == "Right":
                    self.replace(p,self.DoubleRightRotation())
                elif self.left.balance == "Left":
                    self.replace(p,self.SingleRightRotation())
                return False # rotationを行うと成長しない
        if self.key < key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                if not self.right.insertx(self, key):
                    return False
            if self.balance == "Left":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Right"
                return True
            elif self.balance == "Right":
                if self.right.balance == "Left":
                    self.replace(p,self.DoubleLeftRotation())
                elif self.right.balance == "Right":
                    self.replace(p,self.SingleLeftRotation())
                return False
        return False # self.key == keyの時は何もしないので成長もしない

    def to_s(self):
        return self.key
    def left_s(self):
        if self.left == None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right == None:
            return None
        return (self.right).key

################################################################
n = int(input())
p = list(map(int,input().split()))
q = [0]*(n+1)
for i in range(n):
    q[p[i]] = i+1
ans = 0
avl = Avltree()
avl.insert(q[n])
for i in range(n-1,0,-1):
    cnt = 0
    v = q[i]
    lo = avl.search_lower(v,None)
    hi = avl.search_higher(v,None)
    #print(lo,hi)
    if lo:
        lo2 = avl.search_lower(lo,0)
        t = lo-lo2
        if hi:
            t *= hi - v
        else:
            t *= n+1 - v
        cnt += t
    if hi:
        hi2 = avl.search_higher(hi,n+1)
        t = hi2 - hi
        if lo:
            t *= v - lo
        else:
            t *= v
        cnt += t
    #print(cnt)
    ans += i*cnt
    avl.insert(v)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int, input().split()))
total = 0
for i in range(n-1):
    no1 = p[i]
    no2 = p[i+1]
    for j in range(i+1, n):
        if p[j] > no1:
            no2 = no1
            no1 = p[j]
        elif p[j] > no2:
            no2 = p[j]
        total += no2
print(total)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n = int(input())
    p = list(map(int,input().split()))

    answer = 0
    for l in range(n-1):
        for r in range(l+1,n):
            answer += sorted(p[l:r+1])[-2]
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
P = [int(i) for i in input().split()]
nlis = [0]*N

for i,j in enumerate(P):
    nlis[N-j] = i

bis = [-1,-1,N,N]

ans = 0
for i,j in enumerate(nlis):
    inser = bisect.bisect_left(bis,j)
    bis.insert(inser,j)
    lis = bis[inser-2:inser+3]
    foo = (lis[4]-lis[3])*(lis[2]-lis[1]) + (lis[3]-lis[2])*(lis[1]-lis[0])
    ans += foo*(N-i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
b = input().split()
sum = 0
for i in range(n-1):
    first = int(b[i])
    second = 0
    for j in range(i+1,n):
        if(second < int(b[j])):
            if(first < int(b[j])):
                second = first
                first = int(b[j])
            else:
                second = int(b[j])
        sum += second
print(sum)

Submission status: Time Limit Exceeded

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

def ncr(n,r,ans=[],result=[]):
    for i in range(len(n)):
        ans1=ans[:]
        ans1.append(n[i])
        n1=n[(i+1):]
        if len(ans1)==r:
            result.append(ans1)
        else:
            ncr(n1, r, ans1, result)
    return result
ans=0
t=ncr(list(range(N)),2)
for i in range(int(N*(N-1)/2)):
    buf=sorted(P[t[i][0]:t[i][1]+1])
    ans+=max(buf[:-1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        N = int(input())
        P = list(map(int, input().split()))
        P.insert(0, 0)
        #print(P)
        
        Sum = 0
        for L in range(1, N):
            for R in range(L+1, N+1):
                X = P[L:R+1]
                X.sort()
                Sum += X[-2]
        print(Sum)
    except:
        break

Submission status: Time Limit Exceeded

Solution code:
import heapq
N = int(input())
P = list(map(int, input().split()))

def xlr(l,r):
    p = P[l: r + 1]
    return heapq.nlargest(2, p)[1]
ans = 0
for l in range(N-1):
    for r in range(l+1,N):
        ans += xlr(l,r)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input() -> str:
    return sys.stdin.readline()
n = int(input())
p = list(map(int, input().split()))
answer = 0
for l in range(1, n):
    for r in range(l + 1, n + 1):
        answer += sorted(p[l - 1:r])[-2]
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
A = [a-1 for a in A]

P = [-1]*n
for i, a in enumerate(A):
    P[a] = i

#print(P)

R = [[n]*2 for _ in range(n)]
q = []
import heapq
heapq.heapify(q)
for i in range(n):
    temp = []
    while q:
        if q[0][0] < A[i]:
            v, j = heapq.heappop(q)
            R[v][j] = i
            if j == 0:
                temp.append((v, j+1))
        else:
            break
    heapq.heappush(q, (A[i], 0))
    for v, j in temp:
        heapq.heappush(q, (v, j))

#print(R)

L = [[-1]*2 for _ in range(n)]
q = []
import heapq
heapq.heapify(q)
for i in reversed(range(n)):
    temp = []
    while q:
        if q[0][0] < A[i]:
            v, j = heapq.heappop(q)
            L[v][j] = i
            if j == 0:
                temp.append((v, j+1))
        else:
            break
    heapq.heappush(q, (A[i], 0))
    for v, j in temp:
        heapq.heappush(q, (v, j))

#print(L)
ans = 0
for i in range(n-1):
    p = P[i]
    l1 = L[i][0]
    l2 = L[i][1]
    r1 = R[i][0]
    r2 = R[i][1]
    ans += ((l1-l2)*(r1-p)+(r2-r1)*(p-l1))*(i+1)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = list(map(int, input().split()))
lis = [0] * (n + 1)
for i in range(n):
    lis[p[i]] = i
l = list(range(-1, n - 1)) + [-1, -1]
r = list(range(1, n + 1)) + [n, n]
ans = 0
for i in range(n):
    ans += (i + 1) * ((lis[i + 1] - l[lis[i + 1]]) * (r[r[lis[i + 1]]] - r[lis[i + 1]]) + (l[lis[i + 1]] - l[l[lis[i + 1]]]) * (r[lis[i + 1]] - lis[i + 1]))
    r[l[lis[i + 1]]] = r[lis[i + 1]]
    l[r[lis[i + 1]]] = l[lis[i + 1]]
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.step = pow(2, n.bit_length() - 1)

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

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    # Return sum for [l, r)
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)

    # Return the minimum i that satisfies a_0 + a_1 + ... + a_i >= x
    def lower_bound(self, x):
        if x <= 0:
            return 0
        i = 0
        k = self.step
        while k:
            if i + k <= self.n and self.data[i + k] < x:
                x -= self.data[i + k]
                i += k
            k >>= 1
        return i


def main():
    N, *P = map(int, read().split())

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

    bit = BIT(N)

    ans = 0
    for n in range(N, 0, -1):
        i = index[n]
        bit.add(i)
        x = bit.get_sum(i)

        left1 = left2 = -1
        right1 = right2 = N
        if x - 2 > 0:
            left2 = bit.lower_bound(x - 2)
        if x - 1 > 0:
            left1 = bit.lower_bound(x - 1)
        if x + 1 <= N - n + 1:
            right1 = bit.lower_bound(x + 1)
        if x + 2 <= N - n + 1:
            right2 = bit.lower_bound(x + 2)

        ans += ((left1 - left2) * (right1 - i) + (right2 - right1) * (i - left1)) * n

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.step = pow(2, n.bit_length() - 1)

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

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    # Return sum for [l, r)
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)

    # Return the minimum i that satisfies a_0 + a_1 + ... + a_i >= x
    def lower_bound(self, x):
        if x <= 0:
            return 0
        i = 0
        k = self.step
        while k:
            if i + k < self.n and self.data[i + k] < x:
                x -= self.data[i + k]
                i += k
            k >>= 1
        return i


def main():
    N, *P = map(int, read().split())

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

    bit = BIT(N)

    ans = 0
    for n in range(N, 0, -1):
        i = index[n]
        bit.add(i)
        x = bit.get_sum(i)

        left1 = left2 = -1
        right1 = right2 = N
        if x - 2 > 0:
            left2 = bit.lower_bound(x - 2)
        if x - 1 > 0:
            left1 = bit.lower_bound(x - 1)
        if x + 1 <= N - n + 1:
            right1 = bit.lower_bound(x + 1)
        if x + 2 <= N - n + 1:
            right2 = bit.lower_bound(x + 2)

        ans += ((left1 - left2) * (right1 - i) + (right2 - right1) * (i - left1)) * n

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *P = map(int, read().split())

    idx = [0] * (N + 1)
    for i, p in enumerate(P):
        idx[p] = i

    left = list(range(-1, N)) + [-1]
    right = list(range(1, N + 1)) + [N, N]

    ans = 0
    for n in range(1, N + 1):
        i = idx[n]
        l1 = left[i]
        l2 = left[l1]
        r1 = right[i]
        r2 = right[r1]

        ans += n * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))

        left[r1] = l1
        right[l1] = r1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

n=int(input())
p=[int(x)-1 for x in input().split()]

p2=sorted(enumerate(p), key=lambda x:x[1], reverse=True)  

ans=0
s=[-1,-1,n,n]
for i,(idx,p) in enumerate(p2):
  t=bisect.bisect_left(s,idx)
  s.insert(t,idx)
  l1=s[t-1]
  l2=s[t-2]
  r1=s[t+1]
  r2=s[t+2]
  ans+=(p+1)*((idx-l1)*(r2-r1)+(r1-idx)*(l1-l2))
              
print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
P = sorted(enumerate(map(int, input().split())), key=lambda x: x[1])[::-1]
used = [-1, P[0][0], N]
ans = 0
for i, p in P[1:]:
    idx = bisect.bisect_left(used, i)
    d = 0
    if idx != 1:
        d += (used[idx] - i) * (used[idx - 1] - used[idx - 2])
    if idx != len(used) - 1:
        d += (i-used[idx - 1]) * (used[idx + 1] - used[idx])
    ans += p * d
    used.insert(idx, i)
print(ans)