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:
n = int(input())
p = list(map(int, input().split()))
dp = [[None]*(n) for _ in range(n-1)]
ans = 0

for i in range(n-1):
    for j in range(i+1, n):
        if i+1 == j:
            a, b = p[i], p[j]
            if a > b: a ,b = b, a
            dp[i][j] = (a, b)
            ans += a
        else:
            c = p[j]
            if dp[i][j-1][0] < c:
                if dp[i][j-1][1] < c:
                    dp[i][j] = (dp[i][j-1][1], c)
                else:
                    dp[i][j] = (c, dp[i][j-1][1])
            else:
                dp[i][j] = dp[i][j-1]
            ans += dp[i][j][0]

for i in range(n-1):
    print(dp[i])

Submission status: Wrong Answer

Solution code:
def resolve():
    n=int(input())
    p=list(map(int,input().split()))
    ans=0
    for i in range(1,n):
        for j in range(i,n):
            ans+=j
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
p = na()
ans = 0

for i in range(n):
    #hidari
    h1 = 1
    h2 = 0
    #migi
    m1 = 1
    m2 = 0
    f1 = True
    f2 = False
    k1 = True
    k2 = False
    for j in range(n):
        if i-j < 0:
            f1 = False
        if i+j > n-1:
            k1 = False
        if f1:
            if not f2:
                if p[i-j] < p[i]:
                    h1 += 1
                else:
                    h2 += 1
                    f2 = True
            else:
                if p[i-j] < p[i]:
                    h2 += 1
        if k1:
            if not k2:
                if p[i+j] < p[i]:
                    m1 += 1
                else:
                    m2 += 1
                    k2 = True
            else:
                if p[i+j] < p[i]:
                    k2 += 1
        if not k1 and not f1:
            break
    ans += p[i]*(h1*m2+m1*h2)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = list(map(int, input().split()))
p2i = {}
for i, p in enumerate(P):
    p2i[p] = i
# ans = 0
ans = 5
prei = p2i[N]
pred = 0
for p in range(N-1, 2, -1):
    i = p2i[p]
    d = abs(prei-i)-1
    ans += p*(p - d + pred)
    prei = i
    pred = d

print(ans)

Submission status: Wrong Answer

Solution code:
num = int(input())
array = list(map(int, input().split()))
sum = 0
top = 0
next = 0

for i in range(num-1):
	for j in range(i+1, num, 1):
		for k in range(i, j+1, 1):
			if k == i:
				top = array[k]
			else:
				if top < array[k]:
					next = top
					top = array[k]
				elif next < array[k]:
					next = array[k]
		sum += next
        
print(sum)

Submission status: Wrong Answer

Solution code:
N=int(input())

listA=list(map(int,input().split()))
print(listA[0:5])

listN=[]
ans=0
for i in range (N):
	for j in range(i+1,N):
		listN=listA[i:j+1]
		listN.remove(max(listN))
		ans+=max(listN)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = list(map(int, input().split()))
p = sorted(p)
score = []

for i in range(n-1):
    score.append(p[i]*(i+1))

print(sum(score))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split())) 
loop = N
P= np.array(A)

w_all = np.array([])
for j in range(loop-1):
    for i in range(loop-1):        
        if 2+i+j<=loop:
            P_v = P[j:2+i+j]
            d = np.max(P_v)
            P_v = np.delete(P_v,np.where(P_v == d))
            w =np.max(P_v)
            w_all = np.append(w_all,w)
        else:
            pass
          
print(w_all.sum())

Submission status: Wrong Answer

Solution code:
def second_max(arr):
    result = list(set(arr))
    return [i for i in reversed(result)][1]


N = int(input())

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

result = 0
for L in range(N-1):
    for R in range(L+1, N):
        # print(P[L:R+1])
        result += second_max(P[L:R+1])

print(result)

Submission status: Wrong Answer

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

N = int(input())
P = list(map(int, input().split()))
P.sort()
ans = 0
j = 1
for i in range(N-1):
    ans += P[i] * j
    j += 1

print(ans)

Submission status: Time Limit Exceeded

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.depth = pow(2, n.bit_length())

    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
        s = 0
        k = 1 << (self.depth - 1)
        while k:
            if i + k <= self.n and s + self.data[i + k] < x:
                i += k
                s += self.data[i]
            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: Time Limit Exceeded

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.depth = pow(2, n.bit_length())

    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 = pow(2, self.depth)
        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: Time Limit Exceeded

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.depth = pow(2, n.bit_length())

    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 = pow(2, self.depth)
        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)
    for i in range(N):
        bit.add(i)

    ans = 0
    for n in range(1, N + 1):
        i = index[n]
        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

        bit.add(i, -1)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ls = [int(i) for i in input().split()]
result = []


for l in range(N-1):
    if ls[l] > ls[l+1]:
        sec_big, biggist = ls[l+1], ls[l]
    else:
        sec_big, biggist = ls[l], ls[l+1]
    result.append(sec_big)
    for r in range(l+2, N):
        if ls[r] > biggist:
            result.append(biggist)
            sec_big = biggist
            biggist = ls[r]
        elif biggist > ls[r] > sec_big:
            result.append(ls[r])
            sec_big = ls[r]
        else:
            result.append(sec_big)
print(sum(result))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ls = [int(i) for i in input().split()]
#N = 5
#ls = [1,2,3,4,5]

dic = {}
result = []

def get_second_large(ls):
  if len(ls) < 2:
    return ls[0]
  else:
    return sorted(ls)[-2]


for l in range(N):
    for r in range(l+1,N):
      tup = tuple(ls[l:r+1])
      if tup not in dic:
        second = get_second_large(ls[l:r+1])
        dic[tup] = second
      result.append(dic[tup])
print(sum(result))

Submission status: Time Limit Exceeded

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

class Node: # ノードの型
    def __init__(self, height, key, x):
        self.height = height # そのノードを根とする部分木の高さ
        self.key    = key    # そのノードのキー
        self.value  = x      # そのノードの値
        self.lst    = None   # 左部分木
        self.rst    = None   # 右部分木 

def height(t): return 0 if t is None else t.height

def bias(t): return height(t.lst) - height(t.rst)

def modHeight(t): t.height = 1 + max(height(t.lst), height(t.rst))

def rotateL(v):
    u = v.rst; t2 = u.lst
    u.lst = v; v.rst = t2
    modHeight(u.lst)
    modHeight(u)
    return u

def rotateR(u):
    v = u.lst; t2 = v.rst
    v.rst = u; u.lst = t2
    modHeight(v.rst)
    modHeight(v)
    return v

def rotateLR(t):
    t.lst = rotateL(t.lst)
    return rotateR(t)

def rotateRL(t):
    t.rst = rotateR(t.rst)
    return rotateL(t)

def keys_sub(t):
    if t is None: return []
    return keys_sub(t.lst) + [t.key] + keys_sub(t.rst)

def values_sub(t):
    if t is None: return []
    return values_sub(t.lst) + [t.value] + values_sub(t.rst)

def items_sub(t):
    if t is None: return []
    return items_sub(t.lst) + [(t.key, t.value)] + items_sub(t.rst)



class AVLMap:
    def __init__(self):
        self.root   = None  # AVL木の根。Node 型
        self.change = False # 修正が必要かを示すフラグ(True:必要, False:不要)
        self.lmax   = None  # 左部分木のキーの最大値
        self.value  = None  # lmax に対応する値
    
    def balanceLi(self, t): return self.balanceL(t)
    def balanceRi(self, t): return self.balanceR(t)

    def balanceLd(self, t): return self.balanceR(t)
    def balanceRd(self, t): return self.balanceL(t)

    def balanceL(self, t):
        if not self.change: return t
        h = height(t)
        if bias(t) == 2:
            if bias(t.lst) >= 0:
                t = rotateR(t)
            else:
                t = rotateLR(t)
        else: modHeight(t)
        self.change = (h != height(t))
        return t

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

     # insert(挿入)    

    def insert(self, key, x): self.root = self.insert_sub(self.root, key, x)

    def insert_sub(self, t, key, x):
        if t is None:
            self.change = True
            return Node(1, key, x)
        elif key < t.key:
            t.lst = self.insert_sub(t.lst, key, x)
            return self.balanceLi(t)
        elif key > t.key:
            t.rst = self.insert_sub(t.rst, key, x)
            return self.balanceRi(t)
        else:
            self.change = False
            t.value = x
            return t

    #重複を許すか許さないかをkeyベースで考える
    def set_append(self, key, x):
        if self.member(key):
            pass
        else:
            self.insert(key, x)
    
    def list_append(self, key, x):
        self.insert(key, x)
        
    # delete(削除)

    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
        elif key < t.key:
            t.lst = self.delete_sub(t.lst, key)
            return self.balanceLd(t)
        elif key > t.key:
            t.rst = self.delete_sub(t.rst, key)
            return self.balanceRd(t)
        else:
            if t.lst is None:
                self.change = True
                return t.rst # 右部分木を昇格させる
            else:
                t.lst = self.delete_max(t.lst) # 左部分木の最大値を削除する
                t.key = self.lmax # 左部分木の削除した最大値で置き換える
                t.value = self.value
                return self.balanceLd(t)

    def delete_max(self, t):
        if t.rst is not None:
            t.rst = self.delete_max(t.rst)
            return self.balanceRd(t)
        else:
            self.change = True
            self.lmax = t.key # 部分木のキーの最大値を保存
            self.value = t.value
            return t.lst # 左部分木を昇格させる

    # member(検索)等
    def member(self, key):
        t = self.root
        while t is not None:
            if key < t.key:
                t = t.lst
            elif key > t.key:
                t = t.rst
            else:
                return True
        return False

    # キーから値を得る。キーがヒットしない場合は None を返す
    def lookup(self, key):
        t = self.root
        while t is not None:
            if key < t.key:
                t = t.lst
            elif key > t.key:
                t = t.rst
            else:
                return t.value
        return None       

    # x以上の最小のキー
    def upper_bound(self, x):
        t = self.root
        res = 0
        ans = None
        while t is not None:
            if x < t.key:
                ans = t.key
                t = t.lst
            elif x > t.key:
                t = t.rst
            else:
                return t.key
        return ans
    
    # x以下の最大のキー
    def lower_bound(self, x):
        t = self.root
        res = 0
        ans = None
        while t is not None:
            if x < t.key:
                t = t.lst
            elif x > t.key:
                ans = t.key
                t = t.rst
            else:
                return int(t.key)
        return ans
            

    def isEmpty(self): return self.root is None

    def clear(self): self.root = None

    def keys(self): return keys_sub(self.root)

    def values(self): return values_sub(self.root)

    def items(self): return items_sub(self.root)

    def size(self): return len(self.keys())




def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    index = [0]*n
    for i in range(n):
        index[a[i]-1] = i
    
    avl = AVLMap()
    
    ans = 0
    avl.insert(index[n-1], n-1)
    for i in range(n-2, -1, -1):
        ind = index[i]
        
        p, q, r, s = 0, 0, 0, 0
        key_upper = avl.upper_bound(ind)
        if key_upper != None:
            p = key_upper
            key_upper = avl.upper_bound(key_upper+1)
            if key_upper == None:
                q = n
            else:
                q = key_upper
        else:
            p = n
            q = n
        
        
        
        
        
        key_lower = avl.lower_bound(ind)
        if key_lower != None:
            r = key_lower
            key_lower = avl.lower_bound(key_lower-1)
            if key_lower == None:
                s = -1
            else:
                s = key_lower
        else:
            r = -1
            s = -1
        

        ans += (i+1)*((p-ind)*(r-s)+(ind-r)*(q-p))
        
        
        avl.insert(ind, i)
    
    print(ans)
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# maspyさんのコード参照
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

# 大きい数から挿入していく
# 左隣にあるインデックスを取得できるようにしておく
# そのために、[1,i]内で書き込んだ数の個数を獲得できるBITを持つ

# BITは一番最後の1ビットの位置が重要なので0ではなく1始まり。そのためNまでループする
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):
    # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
    # 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
    left = 0
    right = N
    while right - left > 1:
        mid = (left + right) // 2
        if BIT_sum(mid) >= x:
            right = mid
        else:
            left = mid
    return right

tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[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
    coef = 0
    if b != 0:
        # [b,c]を含むようにする。(a,b) と(c,d)が自由
        coef += (b-a) * (d-c)
    if d != 0:
        # [c,d]を含むようにする。
        coef += (e-d) * (c-b)
    answer += x * coef
print(answer)

Submission status: Time Limit Exceeded

Solution code:

def ans(l,r,t):
	p = t[:]
	q=[]
	for i in range(l, r + 1):
		q.append(p[i])
	q.sort(reverse=True)
	return(q[1])
	
	
n = int(input())
p = list(map(int, input().split()))

c=0

for l in range(n-1):
	for r in range(l+1, n):
		c += ans(l, r, p)
		
print(c)

Submission status: Time Limit Exceeded

Solution code:

def ans(l,r,t):
	p = t[:]
	mi = l
	for i in range(l, r + 1):
		if p[i] >p[mi]:
			mi = i
	p[l], p[mi] =p[mi],p[l]
	mj = l + 1
	for j in range(l + 1, r+1):

		if p[j] > p[mj]:
			mj = j
	p[l+1], p[mj] = p[mj],p[l+1]
	return(p[l+1])
	
	
n = int(input())
p = list(map(int, input().split()))

c=0

for l in range(n-1):
	for r in range(l+1, n):
		c += ans(l, r, p)
		
print(c)

Submission status: Time Limit Exceeded

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

pos=[-1]*(N+1)

for i in range(N):
  pos[P[i]]=i
  
called=[-1,-1,pos[N],N,N]
ans=0
for i in range(N-1,0,-1):
  hoge=pos[i]
  r=bisect.bisect_left(called,hoge)
  R=called[r]
  RR=called[r+1]
  L=called[r-1]
  LL=called[r-2]
  ans+=i*((RR-R)*(hoge-L)+(L-LL)*(R-hoge))
  called=called[:r]+[hoge]+called[r:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        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:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < 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

def main():
    n = int(input())
    P = list(map(int, input().split()))
    ans = 0
    arr = [[P[i], i] for i in range(n)]
    arr.sort(key=lambda x: -x[0])
    seg = SegTree(0, n, [0]*n)
    for v, idx in arr:
        seg.update(idx, 1)
        if idx < n-1 and seg.query(idx+1, n) > 0:
            L, R = idx, n
            while L+1 < R:
                M = (L+R)//2
                if seg.query(idx+1, M+1) < 1:
                    L = M
                else:
                    R = M
            x = R
            L, R = x, n
            while L+1 < R:
                M = (L+R)//2
                if seg.query(idx+1, M+1) < 2:
                    L = M
                else:
                    R = M
            r_range = R - x
            L, R = -1, idx
            while L+1 < R:
                M = (L+R+1)//2
                if seg.query(M, idx) == 0:
                    R = M
                else:
                    L = M
            l_range = idx - L
            ans += v * l_range * r_range
            #print("right : ", v, l_range, r_range)
        if 0 < idx and seg.query(0, idx) > 0:
            L, R = idx, n
            while L+1 < R:
                M = (L+R)//2
                if seg.query(idx+1, M+1) == 0:
                    L = M
                else:
                    R = M
            r_range = R - idx
            L, R = 0, idx
            while L+1 < R:
                M = (L+R)//2
                if seg.query(M, idx) < 1:
                    R = M
                else:
                    L = M
            x = L
            L, R = -1, x
            while L+1 < R:
                M = (L+R+1)//2
                if seg.query(M, idx) < 2:
                    R = M
                else:
                    L = M
            l_range = x - L
            ans += v * l_range * r_range
            #print("right : ", v, l_range, r_range)
        #print("ans : ", v, ans)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


def main():
    N = int(input())
    P = list(map(int, input().split(' ')))
    Q = [0] + P + [N + 1]
    index_q = [0 for _ in range(len(Q))]
    for i, q in enumerate(Q):
        index_q[q] = i
    I = [0, 0, N + 1, N + 1]
    ans = 0
    for c in range(N, 0, -1):
        i = index_q[c]
        j = bisect.bisect_left(I, i)
        w, x, y, z = I[j - 2], I[j - 1], I[j], I[j + 1]
        ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
        I.append(i)
        I.sort()
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


def main():
    N = int(input())
    P = list(map(int, input().split(' ')))
    Q = [0] + P + [N + 1]
    I = [0, 0, N + 1, N + 1]
    ans = 0
    for c in range(N, 0, -1):
        i = Q.index(c)
        j = bisect.bisect_left(I, i)
        w, x, y, z = I[j - 2], I[j - 1], I[j], I[j + 1]
        ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
        I.append(i)
        I.sort()
    print(ans)


if __name__ == '__main__':
    main()