Problem:


Score: 500 points

Problem Statement

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

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

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

Constraints

 2 \le N \le 10^5 

 1 \le P_i \le N 

 P_i \neq P_j  (i \neq j)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N

Output

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

Sample Input 1

3
2 3 1

Sample Output 1

5

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

Sample Input 2

5
1 2 3 4 5

Sample Output 2

30

Sample Input 3

8
8 2 7 3 4 5 6 1

Sample Output 3

136



Sample input:
3
2 3 1


Sample output:
5

Submission status: Accepted

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

LL = [0] + [i for i in range(N+1)]
RR = [i+1 for i in range(N+1)] + [N+1]

E = [(v, i+1) for i, v in enumerate(P)]
E.sort()

ans = 0
for v, i in E:
    l0 = LL[i]; l1 = LL[l0]

    r0 = RR[i]; r1 = RR[r0]

    LL[RR[i]], RR[LL[i]] = LL[i], RR[i]

    ans += ((r1 - r0) * (i - l0) + (r0 - i) * (l0 - l1)) * v
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = list(map(int, input().split()))
R = list(range(N))
L = list(range(N))
I = [-1] * (N+1)
for i, p in enumerate(P):
    I[p] = i

ans = 0
for n, idx in enumerate(I[1:], 1):
    l = idx-1
    if l>=0:
        l = L[l]
    r = idx+1
    if r<N:
        r = R[r]
    L[r-1] = l
    R[l+1] = r

    if l>=0:
        l2 = l-1
        if l2>=0:
            l2 = L[l2]
        ans += n * (l-l2) * (r-idx)
    if r<N:
        r2 = r+1
        if r2<N:
            r2 = R[r2]
        ans += n * (idx-l) * (r2-r)
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
A = [a-1 for a in A]
AINV=[0]*N

for i,x in enumerate(A):
    AINV[x]=i

ANS = 0

# BIT(BIT-indexed tree)

LEN=N# 必要なら座標圧縮する

BIT=[0]*(LEN+1)# 1-indexedなtree

def update(v,w):# index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v))# 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v):# [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v))# 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

update(AINV[-1]+1,1)

ANS=0

def search(score):
    if score<=0:
        return 0
    if score>getvalue(N):
        return N+1

    MIN=1
    MAX=N

    while MIN!=MAX:
        x=(MIN+MAX)//2

        if getvalue(x)>=score:
            MAX=x
        else:
            MIN=x+1

    return MIN
            

for i in range(N-2,-1,-1):
    update(AINV[i]+1,1)

    sc=getvalue(AINV[i]+1)


    ANS+=(i+1)*((search(sc)-search(sc-1))*(search(sc+2)-search(sc+1))+(search(sc-1)-search(sc-2))*(search(sc+1)-search(sc)))


print(ANS)

Submission status: Accepted

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

iPs = [0] * (N+1)
for iP, A in enumerate(Ps):
    iPs[A] = iP

ans = 0
iLs = list(range(N+1))
iRs = list(range(N+1))
for P in range(1, N+1):
    i = iPs[P]
    iL, iR = iLs[i], iRs[i]
    if iL <= 1:
        iL2 = 0
    else:
        iL2 = iLs[iL-1]
    if iR >= N-2:
        iR2 = N-1
    else:
        iR2 = iRs[iR+1]
    num = 0
    if iL != 0:
        num += (iL-iL2)*(iR-i+1)
    if iR != N-1:
        num += (i-iL+1)*(iR2-iR)
    ans += P * num
    iLs[iR+1] = iL
    iRs[iL-1] = iR

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = [0]+list(map(int,input().split()))+[N+1]
ans = 0
b = [0]*(N+2)
for i in range(N+2):
    b[P[i]] = i
l1 = [max(0,i-1) for i in range(N+2)]
l2 = [max(0,i-2) for i in range(N+2)]
r1 = [min(N+1,i+1) for i in range(N+2)]
r2 = [min(N+1,i+2) for i in range(N+2)]

for i in range(N+1):
    m = b[i]
    x2,x1,y1,y2 = l2[m],l1[m],r1[m],r2[m]
    hoge= i*(abs((m-x1)*(y2-y1)) + abs((y1-m)*(x1-x2)))
    ans += hoge
    #x1
    r1[x1] = y1
    r2[x1] = y2
    #y1
    l1[y1] = x1
    l2[y1] = x2
    #x2
    r1[x2] = x1
    r2[x2] = y1
    #y2
    l1[y2] = y1
    l2[y2] = x1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
P = list(map(int, sys.stdin.readline().split()))
N += 1
P = [0] + P

def test(A):
    N = len(A)
    ret = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            b = A[i: j + 1].copy()
            b.sort()
            ret += b[-2]
    return ret


#
# ans = defaultdict(list)
# for a in itertools.permutations(range(1, 5)):
#     t = test(list(a))
#     ans[t].append(a)
#
# for k in sorted(ans.keys()):
#     print('--- {} ---'.format(k))
#     for v in ans[k]:
#         print(v)


# ans = test(P)
# print(ans)


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


def bisect_left_callable(fn, x, lo, hi):
    """
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


def argsort(li):
    return [i for _, i in sorted([(a, i) for i, a in enumerate(li)], reverse=True)]


bit = BinaryIndexedTree(size=N)

idx = argsort(P)
ans = 0
for i in idx[:-1]:
    cnt = bit.sum(i)
    # cnt が 1 減る場所
    l1 = bisect_left_callable(lambda k: bit.sum(k), cnt, lo=0, hi=i)
    l2 = bisect_left_callable(lambda k: bit.sum(k), cnt - 1, lo=0, hi=i)
    # 1 増える場所
    r1 = bisect_left_callable(lambda k: bit.sum(k), cnt + 1, lo=i + 1, hi=N)
    r2 = bisect_left_callable(lambda k: bit.sum(k), cnt + 2, lo=i + 1, hi=N)

    a = (r1 - i) * (l1 - l2)
    b = (i - l1) * (r2 - r1)
    # print(P[i], l1, l2, r1, r2, a, b)
    # print(P[i], a + b)

    ans += P[i] * (a + b)
    bit.add(i, 1)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, P: "List[int]"):
    pos = {n: i+1 for i, n in enumerate(P)}
    L1 = list(range(-1, N+1))
    L1[0] = 0
    L2 = list(range(-2, N))
    L2[0] = 0
    L2[1] = 0
    R1 = list(range(1, N+3))
    R1[-1] = N+1
    R2 = list(range(2, N+4))
    R2[-1] = N+1
    R2[-2] = N+1

    res = 0
    for i in range(1, N+1):
        s = pos[i]
        num = 0
        num += (R2[s] - R1[s]) * (s - L1[s])
        num += (L1[s] - L2[s]) * (R1[s] - s)
        res += i * num

        L1[R1[s]] = L1[s]
        L2[R1[s]] = L2[s]
        L2[R2[s]] = L1[s]
        R1[L1[s]] = R1[s]
        R2[L1[s]] = R2[s]
        R2[L2[s]] = R1[s]

    print(res)        
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

class Searchable_BIT():
    def __init__(self,N):
        self.N = N
        self.node = [0]*(self.N+1)
        self.cnt = 0

    def add(self,a): # 要素 x を追加
        x = a
        self.cnt += 1
        while x <= self.N:
            self.node[x] += 1
            x += x & -x

    def delete(self,x): # 要素 x を削除
        self.cnt -= 1
        while x <= self.N:
            self.node[x] -= 1
            x += x & -x

    def count(self,x): # x以下の要素数
        tmp = 0
        while x > 0:
            tmp += self.node[x]
            x -= x & -x
        return tmp

    def get_maxval(self):
        return self.get_lower_i(self.cnt)

    def get_lower_i(self,i): # i 番目に小さい要素を取得
        NG = -1
        OK = self.N+1
        while OK-NG > 1:
            mid = (OK+NG)//2
            #print(OK,NG,self.count(mid))
            if self.count(mid) >= i:
                OK = mid
            else:
                NG = mid
        return OK

N = inp()
PP = inpl()
inds = [0]*(N+1)
for i,P in enumerate(PP):
    inds[P] = i+1

BIT = Searchable_BIT(N)
ans = 0
for i in reversed(range(1,N+1)):
    ind = inds[i]
    BIT.add(ind)
    cnt = BIT.count(ind)
    Lind1 = BIT.get_lower_i(cnt-1)
    Lind2 = BIT.get_lower_i(cnt-2)
    Rind1 = BIT.get_lower_i(cnt+1)
    Rind2 = BIT.get_lower_i(cnt+2)
    L1 = ind   - Lind1
    L2 = Lind1 - Lind2
    R1 = Rind1 -   ind
    R2 = Rind2 - Rind1
    #print(i,Lind2,Lind1,ind,Rind1,Rind2)
    if Rind1 != N+1:
        ans += i * L1 * R2
    if Lind1 != 0:
        ans += i * L2 * R1


print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = [int(a)-1 for a in input().split()]
INV = [0] * N
for i in range(N):
    INV[P[i]] = i

NN = 17
MA = [-1] * ((1<<NN+1)-1)
MI = [N] * ((1<<NN+1)-1)

def update(a, x):
    i = (1<<NN) - 1 + a
    MI[i] = x
    MA[i] = x
    while True:
        i = (i-1) // 2
        MI[i] = min(MI[2*i+1], MI[2*i+2])
        MA[i] = max(MA[2*i+1], MA[2*i+2])
        if i == 0:
            break

def rangemin(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    mi = N
    while l < r:
        if l%2:
            mi = min(mi, MI[l-1])
            l += 1
        if r%2:
            r -= 1
            mi = min(mi, MI[r-1])
        l >>= 1
        r >>= 1
    return mi
def rangemax(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    ma = -1
    while l < r:
        if l%2:
            ma = max(ma, MA[l-1])
            l += 1
        if r%2:
            r -= 1
            ma = max(ma, MA[r-1])
        l >>= 1
        r >>= 1
    return ma
ans = 0
for i in INV[::-1]:
    l1 = rangemax(0, i)
    l2 = rangemax(0, l1)
    r1 = rangemin(i+1, N+1)
    r2 = rangemin(r1+1,N+1)
    pre = ans
    ans += (P[i]+1) * ((i-l1) * (r2-r1) + (l1-l2) * (r1-i))
    update(i, i)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = list(map(int, input().split()))
R = list(range(N))
L = list(range(N))
I = [-1] * (N+1)
for i, p in enumerate(P):
    I[p] = i

ans = 0
for n, idx in enumerate(I[1:], 1):
    l = idx-1
    while l>=0 and l!=L[l]:
        l = L[l]
    r = idx+1
    while r<N and r!=R[r]:
        r = R[r]
    L[idx] = l
    R[idx] = r

    if l != -1:
        l2 = l-1
        while l2>=0 and l2!=L[l2]:
            l2 = L[l2]
        ans += n * (l-l2) * (r-idx)
    if r != N:
        r2 = r+1
        while r2<N and r2!=R[r2]:
            r2 = R[r2]
        ans += n * (idx-l) * (r2-r)
print(ans)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.N = n
        self.n = 1<<n.bit_length()
        self.data = [0] * (self.n + 1)
        self.num = 0
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i
        self.num+=1
    def search(self, value):
        if value<1:
            return 0
        if value >self.num:
            return self.N+1
        x,sx = 0,0
        step = self.n
        while step:
            y = x+step
            sy = sx+self.data[y]
            if sy < value:
                x,sx = y,sy
            step >>= 1
        return x+1

N = int(input())
P = list(map(int, input().split()))
index = [-1]*N
BIT = BIT(N)
ans = 0
for i in range(N):
    index[P[i]-1] = i+1
for num, p in enumerate(range(N, 0, -1)):
    i = index[p-1]
    BIT.add(i, 1)
    j = BIT.sum(i-1)+1
    a = BIT.search(j-2)
    b = BIT.search(j-1)
    c = BIT.search(j+1)
    d = BIT.search(j+2)
    ans+=p*((b-a)*(c-i)+(d-c)*(i-b))
print(ans)

Submission status: Accepted

Solution code:
import heapq


N = int(input())

P = list(map(int,input().split()))


Llis = []
Rlis = []

for i in range(N):

    Llis.append([N,N])
    Rlis.append([N,N])
    P[i] -= 1


LQ1 = []
LQ2 = []

for i in range(N):

    while len(LQ2) > 0 and LQ2[0][0] < P[i]:
        Llis[LQ2[0][1]][1] = i
        heapq.heappop(LQ2)

    while len(LQ1) > 0 and LQ1[0][0] < P[i]:
        Llis[LQ1[0][1]][0] = i
        heapq.heappush(LQ2,LQ1[0])
        heapq.heappop(LQ1)

    heapq.heappush(LQ1,[P[i],i])

P.reverse()
LQ1 = []
LQ2 = []

for i in range(N):

    while len(LQ2) > 0 and LQ2[0][0] < P[i]:
        Rlis[LQ2[0][1]][1] = i
        heapq.heappop(LQ2)

    while len(LQ1) > 0 and LQ1[0][0] < P[i]:
        Rlis[LQ1[0][1]][0] = i
        heapq.heappush(LQ2,LQ1[0])
        heapq.heappop(LQ1)

    heapq.heappush(LQ1,[P[i],i])





Rlis.reverse()
#print (Llis,Rlis)

ans = 0
P.reverse()

for i in range(N):

    Llenge = Llis[i][1] - Llis[i][0]
    Rlenge = 1 + max(0,i - (N - Rlis[i][0]))

    ans += (P[i]+1) * Llenge * Rlenge
    #print (P[i] , Llenge , Rlenge)

P.reverse()
Rlis.reverse()
Llis.reverse()

for i in range(N):

    Rlenge = Rlis[i][1] - Rlis[i][0]
    Llenge = 1 + max(0,i - (N - Llis[i][0]))

    ans += (P[i]+1) * Llenge * Rlenge
    #print (P[i],Llenge,Rlenge)

print (ans)

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

    def ope(self, x, y):
        return x + y

    def update(self, i, v):
        while i <= self.n:
            self.data[i] = self.ope(self.data[i], v)
            i += i & -i

    def query(self, i):
        ret = 0
        while 0 < i:
            ret = self.ope(self.data[i], ret)
            i &= i - 1
        return ret

    def lowerBound(self, w):
        if w <= 0: return 0
        x, k = 0, 2**self.n.bit_length()
        while k:
            if x+k <= self.n and self.data[x+k] < w:
                w -= self.data[x+k]
                x += k
            k >>= 1
        return x + 1

n = int(input())
p = list(map(int, input().split()))
pos = [0]*n
for i, pi in enumerate(p):
    pos[pi-1] = i

bit1 = BIT(n)
bit2 = BIT(n)
ans = 0
for pi in range(n, 0, -1):
    i = pos[pi-1]
    cur = bit1.query(i+1)
    if cur == 0:
        left_0 = i+1
        left_1 = 0
    else:
        tmp = bit1.lowerBound(cur)
        tmp2 = bit1.lowerBound(cur-1)
        left_0 = i+1-tmp
        left_1 = tmp-tmp2
    # 更新
    bit1.update(i+1, 1)
    j = n-i-1
    cur = bit2.query(j+1)
    if cur == 0:
        right_0 = j+1
        right_1 = 0
    else:
        tmp = bit2.lowerBound(cur)
        tmp2 = bit2.lowerBound(cur-1)
        right_0 = j+1-tmp
        right_1 = tmp-tmp2
    # 更新
    bit2.update(j+1, 1)
    ans += pi*(left_0*right_1 + left_1*right_0)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = list(map(int, input().split()))
R = list(range(N))
L = list(range(N))
I = [-1] * (N+1)
for i, p in enumerate(P):
    I[p] = i

ans = 0
for n, idx in enumerate(I[1:], 1):
    #print(f"n={n}, idx={idx}")
    l = idx-1
    while l>=0 and l!=L[l]:
        l = L[l]
    r = idx+1
    while r<N and r!=R[r]:
        r = R[r]
    L[idx] = l
    R[idx] = r

    if l != -1:
        l2 = l-1
        while l2>=0 and l2!=L[l2]:
            l2 = L[l2]
        #print(f"n * (l-l2) * (r-idx) = {n * (l-l2) * (r-idx)}")
        #print(l, l2)
        ans += n * (l-l2) * (r-idx)
        #L[l] = l2
    if r != N:
        r2 = r+1
        while r2<N and r2!=R[r2]:
            r2 = R[r2]
        #print(f"n * (idx-l) * (r2-r) = {n * (idx-l) * (r2-r)}")
        ans += n * (idx-l) * (r2-r)
        #R[r] = r2
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
class PMS:
    #1-indexed
    def __init__(self, A, B, issum = False):
        #Aに初期状態の要素をすべて入れる,Bは値域のリスト
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        if issum:
            self.sumtree = [0] * (self.size + 1)
            Ssum = [0] + list(accumulate([CA[self.X[i]]*self.X[i] for i in range(self.size)]))
            for i in range(1, 1+self.size):
                self.sumtree[i] = Ssum[i] - Ssum[i - (i&-i)]
    
    def compress(self, L):
        #座圧
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        # 1-indexed
        return L2, C
    
    def leng(self):
        #今入っている個数を取得
        return self.count(self.X[-1])
    
    def count(self, v):
        #v(Bの元)以下の個数を取得
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        #v(Bの元である必要はない)未満の個数を取得
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        #v(Bの元である必要はない)以下の個数を取得
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, v, x):
        #vをx個入れる,負のxで取り出す,iの個数以上取り出すとエラーを出さずにバグる
        i = self.comp[v]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def get(self, i):
        # i番目の値を取得
        if i <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < i:
                s += k
                i -= self.tree[s]
            k //= 2
        return self.X[s]
    
    def gets(self, v):
        #累積和がv以下となる最大のindexを返す
        v1 = v
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.sumtree[s+k] < v:
                s += k
                v -= self.sumtree[s]
            k //= 2
        if s == self.size:
            return self.leng()
        return self.count(self.X[s]) + (v1 - self.countsum(self.X[s]))//self.X[s]
    
    def addsum(self, i, x):
        #sumを扱いたいときにaddの代わりに使う
        self.add(i, x)
        x *= i
        i = self.comp[i]
        while i <= self.size:
            self.sumtree[i] += x
            i += i & -i
    
    def countsum(self, v):
        #v(Bの元)以下のsumを取得
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.sumtree[i]
            i -= i & -i
        return s
    
    def getsum(self, i):
        #i番目までのsumを取得
        x = self.get(i)
        return self.countsum(x) - x*(self.count(x) - i)




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

T = PMS([0, 0, N+1, N+1], list(range(-1, N+3)))

K = [None]*(N+4)
K[-1] = 0
K[0] = 0
K[N+1] = N+1
K[N+2] = N+1

for i in range(N):
    p = P[i]
    K[p] = i+1

ans = 0

for j in range(N, 0, -1):
    k = K[j]
    T.add(k, 1)
    cnt = T.count(k)
    a = T.get(cnt-2)
    b = T.get(cnt-1)
    c = k
    d = T.get(cnt+1)
    e = T.get(cnt+2)
    ans += j*((e-d)*(c-b) + (d-c)*(b-a))

print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()

st = []
ans = 0
gans = 0
for i in range(n):
    v = a[i]
    l = 0
    bst = []
    while len(st) > 0 and st[-1][1] < v:
        h = st.pop(-1)
        ans -= h[1] * h[2]
        if h[0] < v:
            h[0], h[1] = v, h[0]
        else:
            h[1] = v
        ans += h[1]*h[2]

        if len(bst) > 0 and bst[-1][0] == h[0] and bst[-1][1] == h[1]:
            bst[-1][2] += h[2]
        else:
            bst.append(h)
    st.extend(bst[::-1])
    st.append([v, 0, 1])
    gans += ans

print(gans)

Submission status: Runtime Error

Solution code:
import sys
import random


class RandomizedBinarySearchTree:
    def __init__(self, n):
        n += 10
        self.n = n
        self.children = [[0] * n, [0] * n]
        self.values = [0] * n
        self.counts = [0] * n
        self.indices = list(range(n - 2, -1, -1))
        self.root = -1

    def merge(self, left_root, right_root):
        children = self.children
        counts = self.counts
        li = left_root
        ri = right_root
        stack = []
        while li != -1 and ri != -1:
            if random.randrange(counts[li] + counts[ri]) < counts[li]:
                stack.append((li, 1))
                li = children[1][li]
            else:
                stack.append((ri, 0))
                ri = children[0][ri]

        i = li if li != -1 else ri
        while stack:
            pi, is_right = stack.pop()
            children[is_right][pi] = i
            counts[pi] = counts[children[0][pi]] + counts[children[1][pi]] + 1
            i = pi

        return i

    def split(self, root, x):
        i = root
        lefts, rights = self.children
        values = self.values
        counts = self.counts
        l_stack = []
        r_stack = []
        while i != -1:
            if x < values[i]:
                r_stack.append(i)
                i = lefts[i]
            else:
                l_stack.append(i)
                i = rights[i]

        li, ri = -1, -1
        while l_stack:
            pi = l_stack.pop()
            rights[pi] = li
            counts[pi] = counts[lefts[pi]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            lefts[pi] = ri
            counts[pi] = counts[ri] + counts[rights[pi]] + 1
            ri = pi

        return li, ri

    def insert(self, x):
        ni = self.indices.pop()
        self.children[0][ni] = self.children[1][ni] = -1
        self.values[ni] = x
        self.counts[ni] = 1

        li, ri = self.split(self.root, x)
        self.root = self.merge(self.merge(li, ni), ri)

    def delete(self, x):
        li, mri = self.split(self.root, x - 1)
        mi, ri = self.split(mri, x)

        if mi == -1:
            self.root = self.merge(li, ri)
            return

        self.indices.append(mi)
        self.root = self.merge(li, ri)
        return

    def upper_bound(self, x, default=-1):
        i = self.root
        lefts, rights = self.children
        values = self.values
        counts = self.counts
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x < values[i]:
                y = values[i]
                c = j + counts[lefts[i]]
                i = lefts[i]
            else:
                j += counts[lefts[i]] + 1
                i = rights[i]
        return y, c

    def lower_bound(self, x, default=-1):
        i = self.root
        lefts, rights = self.children
        values = self.values
        counts = self.counts
        y = default
        c = counts[i]
        j = 0
        while i != -1:
            if x <= values[i]:
                y = values[i]
                c = j + counts[lefts[i]]
                i = lefts[i]
            else:
                j += counts[lefts[i]] + 1
                i = rights[i]
        return y, c

    def get_k_th(self, k, default=-1):
        i = self.root
        children = self.children
        values = self.values
        counts = self.counts
        if counts[i] <= k:
            return default
        j = k
        while i != -1:
            left_count = counts[children[0][i]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[0][i]
            else:
                j -= left_count + 1
                i = children[1][i]
        return default

    def debug_print(self):
        print('Lefts ', self.children[0])
        print('Rights', self.children[1])
        print('Values', self.values)
        print('Counts', self.counts)
        self._debug_print(self.root, 0)

    def _debug_print(self, i, depth):
        if i != -1:
            self._debug_print(self.children[0][i], depth + 1)
            print('      ' * depth, self.values[i], self.counts[i])
            self._debug_print(self.children[1][i], depth + 1)


q = int(input())
rbst = RandomizedBinarySearchTree(q)
for line in sys.stdin:
    t, x = map(int, line.split())
    if t == 1:
        rbst.insert(x)
    else:
        y = rbst.get_k_th(x - 1)
        print(y)
        rbst.delete(y)