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: Runtime Error

Solution code:
class Avltree:
    """ Avl木を表現するクラス """
    def __init__(self):
        self.avl = [None,None,None,0]

    def node(self,key):
        return [None,key,None,0]

    # search(x) xが存在するならTrueをしないならFalseを返す
    # 使用法 Instance.search(x)
    def search(self,key,avl=None):
        if avl == None:
            avl = self.avl
        if key == avl[1]:
            return True
        elif key < avl[1]:
            if avl[0] == None:
                return False
            else:
                return self.search(key,avl[0])
        elif avl[1] < key:
            if avl[2] == None:
                return False
            else:
                return self.search(key,avl[2])
    
    # key未満で最大の要素を検索する。なければNoneを返す。
    # 使用法 Instance.search_lower(x)
    def search_lower(self,key,key_lower=None,avl=0):
        if avl == 0:
            avl = self.avl
        if avl == None:
            return key_lower
        elif key < avl[1]:
            if avl[0] == None:
                return key_lower
            else:
                return self.search_lower(key,key_lower,avl[0])
        elif avl[1] < key:
            key_lower = avl[1]
            if avl[2] == None:
                return key_lower
            else:
                return self.search_lower(key,key_lower,avl[2])
        #avl[1] == keyの場合
        if avl[0] == None:
            return key_lower
        else:
            if key_lower == None:
                return self.end_higher(avl[0][1],avl[0])
            else:
                return max(key_lower,self.end_higher(avl[0][1],avl[0]))
    
    # keyより大きい最小の要素を検索する。なければNoneを返す。
    # 使用法 Instance.search_higher(x)
    def search_higher(self,key,key_higher=None,avl=0):
        if avl == 0:
            avl = self.avl
        if avl == None:
            return key_higher
        if  key < avl[1]:
            key_higher = avl[1]
            if avl[0] == None:
                return key_higher
            else:
                return self.search_higher(key,key_higher,avl[0])
        if avl[1] < key:
            if avl[2] == None:
                return key_higher
            else:
                return self.search_higher(key,key_higher,avl[2])
        #self.key == keyの場合
        if avl[2] == None:
            return key_higher
        else:
            if key_higher == None:
                return self.end_lower(avl[2][1],avl[2])
            else:
                return min(key_higher,self.end_lower(avl[2][1],avl[2]))
    
    def end_lower(self,end_lower_key,avl=None):
        if avl == None:
            avl = self.avl
        if avl[0] == None:
            return end_lower_key
        else:
            end_lower_key = avl[0][1]
            return self.end_lower(end_lower_key,avl[0])
    def end_higher(self,end_higher_key,avl=None):
        if avl == None:
            avl = self.avl
        if avl[2] == None:
            return end_higher_key
        else:
            end_higher_key = avl[2][1]
            return self.end_higher(end_higher_key,avl[2])

    def DoubleRightRotation(self,avl):
        tl = avl[0]
        avl[0] = tl[2][2]
        tl[2][2] = avl # selfはそのノード
        tlr = tl[2]
        tl[2] = tlr[0]
        tlr[0] = tl
        if tlr[3] == 1:
            tlr[2][3] = 2
            tlr[0][3] = 0
        elif tlr[3] == 2:
            tlr[2][3] = 0
            tlr[0][3] = 1
        elif tlr[3] == 0:
            tlr[2][3] = 0
            tlr[0][3] = 0
        tlr[3] = 0
        return tlr

    def DoubleLeftRotation(self,avl):
        tr = avl[2]
        avl[2] = tr[0][0]
        tr[0][0] = avl
        trl = tr[0]
        tr[0] = trl[2]
        trl[2] = tr
        if trl[3] == 2:
            trl[0][3] = 1
            trl[2][3] = 0
        elif trl.balance == 1:
            trl[0][3] = 0
            trl[2][3] = 2
        elif trl.balance == 0:
            trl[0][3] = 0
            trl[2][3] = 0
        trl[3] = 0
        return trl

    def SingleLeftRotation(self,avl):
        tr = avl[2]
        tr[3] = 0
        avl[3] = 0
        avl[2] = tr[0]
        tr[0] = avl
        return tr

    def SingleRightRotation(self,avl):
        tl = avl[0]
        tl[3] = 0
        avl[3] = 0
        avl[0] = tl[2]
        tl[2] = avl
        return tl

    def replace(self,p,v,avl): # 親ノードpの下にある自分(avl)をvに置き換える。
        if p[0] is avl:
            p[0] = v
        else :
            p[2] = v
    
    # 木に要素を追加する。
    # 使用法 Instance.insert(x)
    def insert(self,key): # rootでのみ呼ばれる挿入
        if self.avl[1] == None: # rootを含むrotationはしないことにする。
            self.avl[1] = key
            return self.avl
        if key < self.avl[1]:
            if self.avl[0] == None:
                self.avl[0] = self.node(key)
            else:
                self.insertx(self.avl,key,self.avl[0])
        elif self.avl[1] < key:
            if self.avl[2] == None:
                self.avl[2] = self.node(key)
            else:
                self.insertx(self.avl,key,self.avl[2])
        else: # key == self.avl[1]:
            pass # do not overwrite
    def insertx(self,p,key,avl): # replaceを呼ぶために一つ上の親を持っているinsert
        if key < avl[1]:
            if avl[0] == None:
                avl[0] = self.node(key)
            else:
                if not self.insertx(avl,key,avl[0]): # 左の木が生長しなければ、
                    return False # 成長しない
            balance = avl[3]
            if balance == 2:
                avl[3] = 0
                return False
            elif balance == 0:
                avl[3] = 1
                return True # 成長した
            elif balance == 1:
                if avl[0][3] == 2:
                    self.replace(p,self.DoubleRightRotation(avl),avl)
               
                return False # rotationを行うと成長しない
        if avl[1] < key:
            if avl[2] == None:
                avl[2] = self.node(key)
            else:
                if not self.insertx(avl,key,avl[2]):
                    return False
            balance = avl[3]
            if balance == 1:
                avl[3] = 0
                return False
            elif balance == 0:
                avl[3] = 2
                return True
            elif balance == 2:
                if avl[2][3] == 1:
                    self.replace(p,self.DoubleLeftRotation(avl),avl)
                elif avl[2][3] == 2:
                    self.replace(p,self.SingleLeftRotation(avl),avl)
                return False
        return False # avl[1] == keyの時は何もしないので成長もしない

    def debug(self):
        print(self.avl)
def main():
    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)
        hi = avl.search_higher(v)
        #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)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import cython

n = int(input())
p = list(map(int, input().split()))

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left, insort_left
from collections import deque
INF = float("inf")


def solve(N: int, P: "List[int]"):

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

    ans = 0
    seq = deque([rev[N]])
    for i in range(N-1, 0, -1):
        j = bisect_left(seq, rev[i])
        seq.insert(j, rev[i])
        if j != 0:
            L, R = seq[j-1], seq[j]
            LL = seq[j-1]-seq[j-2] if j-2 >= 0 else seq[j-1]+1
            RR = seq[j+1]-seq[j] if j+1 <= N-i else N-seq[j]
            ans += i*(LL*RR)

        if j+1 <= N-i:
            L, R = seq[j], seq[j+1]
            LL = seq[j]-seq[j-1] if j-1 >= 0 else seq[j]+1
            RR = seq[j+2]-seq[j+1] if j+2 <= N-i else N-seq[j+1]
            ans += i*(LL*RR)

    print(ans)

    return


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: Runtime Error

Solution code:
import numpy as np


N = int(input())
P = np.array(input().split(), np.int32)

N_num = np.arange(N)
xx, yy = np.meshgrid(N_num, N_num)
num_comb = np.c_[xx.flatten(), yy.flatten()]

LR_pair = num_comb[np.where(num_comb[:, 0] < num_comb[:, 1])]
second_max = [np.sort(P[p[0]:p[1]+1])[-2] for p in LR_pair]
print(np.sum(second_max))

Submission status: Runtime Error

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 = 5
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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left, insort_left
from collections import deque
INF = float("inf")


def solve(N: int, P: "List[int]"):

    # 番号pは何番目か 0-index
    rev = [0]*(N+1)
    for i, p in enumerate(P):
        rev[p] = i

    ans = 0
    seq = deque([rev[N]])
    for i in range(N-1, 0, -1):
        j = bisect_left(seq, rev[i])
        seq.insert(j, rev[i])
        # print(seq, j)
        if j != 0:
            L, R = seq[j-1], seq[j]
            LL = seq[j-1]-seq[j-2] if j-2 >= 0 else seq[j-1]+1
            RR = seq[j+1]-seq[j] if j+1 <= N-i else N-seq[j]
            ans += i*(LL*RR)
            # print("addA", i*(LL*RR), LL, RR)

        if j != N-i:
            L, R = seq[j], seq[j+1]
            LL = seq[j]-seq[j-1] if j-1 >= 0 else seq[j]+1
            RR = seq[j+2]-seq[j+1] if j+2 <= N-i else N-seq[j+1]
            ans += i*(LL*RR)
            # print("addB", i*(LL*RR), LL, RR)

        # print("ans", ans)
        # if i == 5:
        # break
    print(ans)

    return


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: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0

for i in range(n-1):
  for j in range(n-i):
    b = a[i:i+j+1]
    b.remove(max(b))
    ans += max(b)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
p = list(map(int, input().split()))

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
p = list(map(int, input().split()))
sum = 0
for L in range(1,n):
  end = 0
  tmp = p[L-1:]
  tmp.sorted(reverse=True)
  second_max = tmp[1]
  for R in range(L+1,n+1):
    if end == 1:
      sum += second_max
    else:
    	tmp = p[L-1:R]
    	tmp.sorted(reverse=True)
    	sum += tmp[1]
    	if tmp[1] == second_max:
      		end = 1

print(sum)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())  
P = np.array(input().split(), dtype=np.int64)

A = np.zeros((N-1, N-1))
B = np.zeros((N-1, N-1))

        
print(int(np.sum(A)))

Submission status: Runtime Error

Solution code:
n = int(input())
p = list(map(int, input().split()))

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

Submission status: Runtime Error

Solution code:
n = int(input())
p = [int(_) for _ in input().split()]

import numpy as np
p = np.array(p)
out = 0
for i in range(len(p)-1):
  for j in range(p):
    out += np.unique(p[i:j])[-2]
print(out)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())  
P = np.array(input().split(), dtype=np.int64)

A = np.zeros((N-1, N-1))
B = np.zeros((N-1, N-1))

for i in range(N-1):
    A[i, i] = min(P[i], P[i+1])
    B[i, i] = max(P[i], P[i+1])

for i in np.arange(N-2)[::-1]:
    for j in np.arange(i+1, N-1):  
        if A[i, j-1] == A[i+1, j]:
            if B[i, j-1] == B[i+1, j]:
                A[i, j] = A[i+1, j]
                B[i, j] = B[i+1, j]
            else:
                A[i, j] = min(B[i, j-1], B[i+1, j])
                B[i, j] = max(B[i, j-1], B[i+1, j])
            
        elif B[i, j-1] == B[i+1, j]:
            A[i, j] = max(A[i, j-1], A[i+1, j])
            B[i, j] = B[i, j-1]
            
        elif B[i, j-1] == A[i+1, j]:
            A[i, j] = A[i+1, j]
            B[i, j] = B[i+1, j]
        
        else:
            A[i, j] = A[i, j-1]
            B[i, j] = B[i, j-1]
        
print(int(np.sum(A)))

Submission status: Runtime Error

Solution code:
#include <cstdint>
#include <iostream>
#include <vector>

int main()
{
	int n;
	std::vector<int> v;
	std::int64_t c = 0;
	
	std::cin >> n;
	
	for (int i = 0; i < n; ++i)
	{
		int x;
		std::cin >> x;
		v.push_back(x);
	}
	
	for (int i = 0; i < n - 1; ++i)
	{
		int x, y;
		
		x = v[i];
		y = 0;
		
		for (int j = i + 1; j < n; ++j)
		{
			if (x < v[j])
			{
				y = x;
				x = v[j];
			}
			else if (y < v[j])
			{
				y = v[j];
			}
			
			c += y;
		}
	}
	
	std::cout << c << std::endl;
	
	return 0;
}

Submission status: Runtime Error

Solution code:
n = int(input())
b = list(map(int, input().split()))
sum = 0
for i in range(n):
  for j in range(i+1, n):
    c = sorted(b[i:j+1])
      sum += c[-2]
print(sum)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())  
P = np.array(input().split(), dtype=np.int64)

def two_min(a,b):
    if a > b:
        return b
    else:
        return a
        
def two_max(a,b):
    if a > b:
        return a
    else:
        return b

A = np.zeros((N-1, N-1))
B = np.zeros((N-1, N-1))

for i in range(N-1):
    A[i, i] = two_min(P[i], P[i+1])
    B[i, i] = two_max(P[i], P[i+1])

for i in np.arange(N-2)[::-1]:
    for j in np.arange(i+1, N-1):  
        if A[i, j-1] == A[i+1, j]:
            if B[i, j-1] == B[i+1, j]:
                A[i, j] = A[i+1, j]
                B[i, j] = B[i+1, j]
            else:
                A[i, j] = two_min(B[i, j-1], B[i+1, j])
                B[i, j] = two_max(B[i, j-1], B[i+1, j])
            
        elif B[i, j-1] == B[i+1, j]:
            A[i, j] = two_max(A[i, j-1], A[i+1, j])
            B[i, j] = B[i, j-1]
            
        elif B[i, j-1] == A[i+1, j]:
            A[i, j] = A[i+1, j]
            B[i, j] = B[i+1, j]
        
        else:
            A[i, j] = A[i, j-1]
            B[i, j] = B[i, j-1]
        
print(int(np.sum(A)))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
P = ([int(x) for x in input().split()])
sumX = 0

for L in range(0, N-1):
    for R in range(L+1, N):
        sP = sorted(P[L:R+1], reverse=True)
        print(sP)
        sumX += sP[1]
    print(P)

print(sumX)

Submission status: Runtime Error

Solution code:
n = int(input())
B = list(map(int, input().split()))
ans = 0
d = 
for i in range(0, n):
  for j in range(i+2, n+1):
    ans += sorted(B[i:j])[-2]
print(ans)

Submission status: Runtime Error

Solution code:
a = int(input())
b = list(map(int,input().split()))
ans = 0
for i in range(1,a):
	for j in range(1,a+1):
		if i < j:
            c = b[i-1:j]           
            c.sort()
            c.reverse()          
            ans += c[1]
        
print(ans)

Submission status: Runtime Error

Solution code:
import itertools

n = int(input())
p = list(map(int, input().split()))

cnt = 0
for l, r in itertools.combinations(range(n-1), range(n,-l,-1)):
  lst = p[l : l + r + 2]
  cnt += sorted(lst)[-2]

print(cnt)

Submission status: Runtime Error

Solution code:
import itertools

n = int(input())
p = list(map(int, input().split()))

cnt = 0
for l, r in itertools.combinations(range(n-1), range(n -l -1)):
  lst = p[l : l + r + 2]
  cnt += sorted(lst)[-2]
    
print(cnt)

Submission status: Runtime Error

Solution code:
a = int(input())
b = List(map(int,input().split()))
ans = 0
for i in range(1,a):
    for j in range(1,a+1):
        if i < j:
            c = b[i-1:j]           
            c.sort()
            c.reverse()          
            ans += c[1]
        
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
P = list(map(int, input()))

ans = 0
for i in range(n):
    ans += i**2

print(ans)

Submission status: Runtime Error

Solution code:
a = int(input())
b = List(map(int,input().split()))
ans = 0

for i in range(1,a):
    for j in range(1,a+1):
        if i < j:
            c = b[i-1:j]
            
            c.sort()
            c.reverse()
            
            ans += c[1]
        
print(ans)

Submission status: Runtime Error

Solution code:
a = int(input())
b = List(map(int,input().split()))
ans = 0

for i in range(1,a):
    for j in range(1,a+1):
        if i < j:
            c = b[i-1:j]
            
            c.sort()
            c.reverse()
            print(c)
            ans += c[1]
        
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0

for i in range(n-1):
  for j in range(n-i-1):
    b = a[i:i+j+1]
    b.pop(max(b))
    ans += max(b)
print(ans)

Submission status: Runtime Error

Solution code:
import itertools

n = int(input())
p = list(map(int, input().split()))

cnt = 0
for l, r in itertools.product(range(n-1), range(n,-l,-1)):
  lst = p[l : l + r + 2]
  cnt += sorted(lst)[-2]

print(cnt)

Submission status: Runtime Error

Solution code:
n = int(inout())
a = list(map(int,input().split()))
ans = 0

for i in range(n-1):
  for j in range(n-i-1):
    b = a[i:i+j+1]
    b.pop(max(b))
    ans += max(b)
print(ans)

Submission status: Runtime Error

Solution code:
import itertools

n = int(input())
p = list(map(int, input().split()))

cnt = 0
for l, r in itertools.product(range(n-1), range(n -l -1)):
  lst = p[l : l + r + 2]
  cnt += sorted(lst)[-2]
    
print(cnt)

Submission status: Runtime Error

Solution code:
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(int(w_all.sum()))

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
#pragma GCC optimize("O3")
#include<bits/stdc++.h>

using namespace std;

typedef long long lll;
#define int lll
typedef long double ld;

typedef pair<int,int> pii;
#define x first
#define y second

const int N=1e5+100;

int p[N],r[N];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>p[i],
        r[p[i]]=i;
    multiset<int,greater<int>> s{0,0,n+1,n+1};
    int ans=0;
    for(int val=n;val>=1;val--)
    {
        int pos=r[val];
        int l=*prev(s.lower_bound(pos));
        int ll=*prev(s.lower_bound(pos),2);
        int r=*s.lower_bound(pos);
        int rr=*next(s.lower_bound(pos));
        int cnt1=(l-ll)*(r-pos);
        int cnt2=(rr-r)*(pos-l);
        ans+=val*(cnt1+cnt2);
        s.insert(pos);
    }
    cout<<ans;
}