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:
import bisect
N=int(input())
P=[0]+list(map(int, input().split()))
C=[0 for _ in range(N+1)]
index=[0 for _ in range(N+1)]
for i in range(1, N+1):
  index[P[i]]=i
l=[0, 0]
r=[N+1, N+1]
for n in range(N, 0, -1):
  C[n]=(l[-1]-l[-2])*(r[0]-index[n])+(index[n]-l[-1])*(r[1]-r[0])
  if index[n]<index[n-1]:
    l.append(index[n])
    if index[n-1]>r[0]:
      i=bisect.bisect_left(r, index[n-1])
      l=l+r[:i]
      r=r[i:]
  else:
    r=[index[n]]+r
    if index[n-1]<l[-1]:
      i=bisect.bisect_right(l, index[n-1])
      r=l[i:]+r
      l=l[:i]
res=0
for i in range(N+1):
  res+=i*C[i]
print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N=int(input())
P=list(map(lambda x:int(x)-1,input().split()))
l=[]
for i in range(N):
    l.append((P[i],i))
l.sort()
ind=[]
for e in l:
    ind.append(e[1])

ans=0
for Pi in reversed(range(N)):
    i=ind[Pi]
    lj=ind[Pi+1:]
    lj+=[-1,-1,N,N]
    lj.sort()
    x=bisect.bisect_left(lj,i)
    a=lj[x-2];b=lj[x-1];c=lj[x];d=lj[x+1]
    ans+=(Pi+1)*((b-a)*(c-i)+(i-b)*(d-c))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
Ps = list(map(int,input().split()))
ans = 0
for i in range(n-1):
  f,s = max(Ps[i:i+2]),min(Ps[i:i+2])
  ans += s
  for j in range(i+2,n):
    if Ps[j] > f:
      s = f
      f = Ps[j]
    elif Ps[j] > s:
      s = Ps[j]
    else:
      pass
    ans += s
print(ans)

Submission status: Time Limit Exceeded

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

idx = [0]*(n+1)
for i in range(n):
    idx[p[i]] = i

total = 0
s =[]
for x in range(n, 0, -1):
    i = idx[x]

    s.append(i)
    s.sort()

    l = [-1] * 2
    r = [n] * 2
    pos = s.index(i)
    if pos > 1:
        l[1] = s[pos - 2]
    if pos > 0:
        l[0] = s[pos - 1]
    if pos < len(s) - 1:
        r[0] = s[pos + 1]
    if pos < len(s) - 2:
        r[1] = s[pos + 2]

    ls = [0] * 2
    ls[0] = i - l[0]
    ls[1] = l[0] - l[1]
    rs = [0] * 2
    rs[0] = r[0] - i
    rs[1] = r[1] - r[0]
    c = ls[0] * rs[1] + ls[1] * rs[0]
    total += c * x

print(total)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
from operator import itemgetter


def solve(n, ppp):
    qqq = sorted(enumerate(ppp), key=itemgetter(1), reverse=True)
    indices = [-1, -1, n, n]
    ans = 0
    for i, p in qqq:
        ii = bisect(indices, i)
        l1, l2 = indices[ii - 2:ii]
        r1, r2 = indices[ii:ii + 2]
        indices = indices[:ii] + [i] + indices[ii:]
        ans += p * ((l2 - l1) * (r1 - i) + (r2 - r1) * (i - l2))
    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=list(map(int,input().split()))
total_ans=0
for i in range(N):
    ans=0
    a=b=c=d=-1
    j=i-1
    while j>=0 and a==-1:
        if P[j]>P[i]:
            if b==-1:
                b=j
            elif a==-1:
                a=j
        j-=1
    j=i+1
    while j<=N-1 and d==-1:
        if P[j]>P[i]:
            if c==-1:
                c=j
            elif d==-1:
                d=j
        j+=1

#    print(f'a={a},b={b},c={c},d={d}')

    if a!=-1!=b:
        if c!=-1!=d:
            ans+=(b-a)*(c-i)+(i-b)*(d-c)
        elif c!=-1==d:
            ans+=(b-a)*(c-i)+(i-b)*(N-c)
        elif c==-1==d:
            ans+=(b-a)*(N-i)
    elif a==-1!=b:
        if c!=-1!=d:
            ans+=(b+1)*(c-i)+(i-b)*(d-c)
        elif c!=-1==d:
            ans+=(b+1)*(c-i)+(i-b)*(N-c)
        elif c==-1==d:
            ans+=(b+1)*(N-i)
    elif a==-1==b:
        if c!=-1!=d:
            ans+=(i+1)*(d-c)
        elif c!=-1==d:
            ans+=(i+1)*(N-c)
    
#    print(ans)
    total_ans+=P[i]*ans
print(total_ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():

	input = sys.stdin.readline

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

	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort(reverse=True)

	x = 0
	largeind = [-1,-1,N,N]
	for i in range(N):
		target = ips[P[i]-1]

		larger = len(largeind)-2
		smaller = 1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		largeind.insert(larger,target)

		L1ind = largeind[larger-1]
		L2ind = largeind[larger-2]
		R1ind = largeind[larger+1]
		R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

	print(x)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, n, init_value):
        self.n = n
        n2 = 1  # nより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [[init_value, init_value] for _ in range(n2 << 1)]
        self.ini = init_value

    def update(self, i, x):
        # 注: 同じiへのクエリは複数来ないことを利用して単純化
        i += self.n2
        self.tree[i][0] = x
        while i > 1:
            i >>= 1
            sti = self.tree[i]
            if sti[0] > x:
                sti[1] = sti[0]
                sti[0] = x
            elif sti[1] > x:
                sti[1] = x

    def get(self, a, b):
        result = [self.ini, self.ini]
        q = [(1, 0, self.n2)]

        while q:
            k, l, r = q.pop()

            if a <= l and r <= b:
                stk = self.tree[k]
                if result[0] > stk[0]:
                    result[1] = min(result[0], stk[1])
                    result[0] = stk[0]
                elif result[1] > stk[0]:
                    result[1] = stk[0]
                continue

            m = (l + r) // 2
            k <<= 1
            if a < m and l < b:
                q.append((k, l, m))
            if a < r and l < m:
                q.append((k + 1, m, r))

        return result


def solve(n, ppp):
    str = SegmentTree(n, n)
    right = []
    for i in range(n - 1, -1, -1):
        p = ppp[i]
        right.append(str.get(p, n))
        str.update(p - 1, i)
    right.reverse()

    ans = 0
    stl = SegmentTree(n, 1)
    for i in range(n):
        p = ppp[i]
        l1, l2 = stl.get(p, n)
        l1, l2 = -l1, -l2
        r1, r2 = right[i]
        ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
        stl.update(p - 1, -i)

    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, n, init_value):
        self.n = n
        n2 = 1  # nより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [[init_value, init_value] for _ in range(n2 << 1)]
        self.ini = init_value

    def update(self, i, x):
        # 注: 同じiへのクエリは複数来ないことを利用して単純化
        i += self.n2
        self.tree[i][0] = x
        while i > 1:
            i >>= 1
            sti = self.tree[i]
            if sti[0] > x:
                sti[1] = sti[0]
                sti[0] = x
            elif sti[1] > x:
                sti[1] = x

    def get(self, a, b):
        result = [self.ini, self.ini]
        self._get(a, b, 1, 0, self.n2, result)
        return result

    def _get(self, a, b, k, l, r, result):
        """
        [a, b)の最小値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        """
        # 範囲外ならINF
        if r <= a or b <= l:
            return
            # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            stk = self.tree[k]
            if result[0] > stk[0]:
                result[1] = min(result[0], stk[1])
                result[0] = stk[0]
            elif result[1] > stk[0]:
                result[1] = stk[0]
            return
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        self._get(a, b, k << 1, l, m, result)
        self._get(a, b, (k << 1) + 1, m, r, result)


def solve(n, ppp):
    str = SegmentTree(n, n)
    right = []
    for i in range(n - 1, -1, -1):
        p = ppp[i]
        right.append(str.get(p, n))
        str.update(p - 1, i)
    right.reverse()

    ans = 0
    stl = SegmentTree(n, 1)
    for i in range(n):
        p = ppp[i]
        l1, l2 = stl.get(p, n)
        l1, l2 = -l1, -l2
        r1, r2 = right[i]
        ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
        stl.update(p - 1, -i)

    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys

def input():
    return sys.stdin.readline()

n = int(input())
P = list(map(int, input().split(" ")))
index = sorted(range(n), key=lambda k: P[k], reverse=True)
bi = [-1,-1,n,n]
bisect.insort(bi,index[0])
C = 0
lc = 0
rc = 0
C1 = 0
for i in index[1:]:
  l = bisect.bisect_left(bi,i)
  lc = bi[l-1] - bi[l-2]
  rc = bi[l] - i
  C1 = lc*rc
  lc = i - bi[l-1]
  rc = bi[l+1] - bi[l]
  C1 += lc*rc
  C += P[i]*C1
  bisect.insort(bi,i)
  
print(C)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():

	input = sys.stdin.readline

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

	ips = [0]*(N)
	for i, val in enumerate(P):
		ips[val-1] = i
	P.sort(reverse=True)

	x = 0
	largeind = [-1,-1,N,N]
	for i in range(N):
		target = ips[P[i]-1]

		larger = len(largeind)
		smaller = -1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		largeind.insert(larger,target)

		L1ind = largeind[larger-1]
		L2ind = largeind[larger-2]
		R1ind = largeind[larger+1]
		R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*P[i]

	print(x)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():

	input = sys.stdin.readline

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

	pp = []
	for i, val in enumerate(P):
		pp.append([i,val])
	pp.sort(key=lambda x:x[1],reverse=True)

	x = 0
	largeind = [-1,-1,N,N]
	for i in range(N):
		target = pp[i][0]
		L1ind, L2ind = -1, -1
		R1ind, R2ind = N, N

		larger = len(largeind)
		smaller = -1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		largeind.insert(larger,target)

		L1ind = largeind[larger-1]
		L2ind = largeind[larger-2]
		R1ind = largeind[larger+1]
		R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*pp[i][1]

	print(x)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():

	input = sys.stdin.readline

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

	pp = []
	for i, val in enumerate(P):
		pp.append([i,val])
	pp.sort(key=lambda x:x[1],reverse=True)

	x = 0
	largeind = []
	for i in range(N):
		target = pp[i][0]
		L1ind, L2ind = -1, -1
		R1ind, R2ind = N, N

		larger = len(largeind)
		smaller = -1
		while larger-smaller!=1:
			medium = int((larger+smaller)/2)
			if largeind[medium]>target:
				larger = medium
			else:
				smaller = medium
		largeind.insert(larger,target)

		if larger-1>=0:
			L1ind = largeind[larger-1]
		if larger-2>=0:
			L2ind = largeind[larger-2]
		if larger+1<=len(largeind)-1:
			R1ind = largeind[larger+1]
		if larger+2<=len(largeind)-1:
			R2ind = largeind[larger+2]

		x += ((L1ind-L2ind)*(R1ind-target) + (target-L1ind)*(R2ind-R1ind))*pp[i][1]

	# print(second_list)
	print(x)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    """
    値をlistで持つSegmentTree
    update(i, x): i(0-indexed)をxで更新
    get(a,b): [a, b)を取得
    """

    def __init__(self, n, ini, merge):
        self.n = n
        n2 = 1  # nより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [ini[:] for _ in range(n2 << 1)]
        self.ini = ini
        self.merge = merge

    def update(self, i, x):
        i += self.n2
        self.merge(self.tree[i], x)
        while i > 1:
            self.merge(x, self.tree[i ^ 1])
            i >>= 1
            sti = self.tree[i]
            sti[0] = x[0]
            sti[1] = x[1]

    def get(self, a, b):
        result = self.ini[:]
        self._get(a, b, 1, 0, self.n2, result)
        return result

    def _get(self, a, b, k, l, r, result):
        """
        [a, b)の最小値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での値
        """
        # 範囲外ならINF
        if r <= a or b <= l:
            return
            # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            self.merge(result, self.tree[k])
            return
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        self._get(a, b, k << 1, l, m, result)
        self._get(a, b, (k << 1) + 1, m, r, result)


def solve(n, ppp):
    def merge_min(x, y):
        """ update x """
        if x[0] <= y[0]:
            if x[1] <= y[0]:
                pass
            else:
                x[1] = y[0]
        elif x[0] <= y[1]:
            x[1] = x[0]
            x[0] = y[0]
        else:
            x[0] = y[0]
            x[1] = y[1]

    def merge_max(x, y):
        """ update x """
        if x[0] >= y[0]:
            if x[1] >= y[0]:
                pass
            else:
                x[1] = y[0]
        elif x[0] >= y[1]:
            x[1] = x[0]
            x[0] = y[0]
        else:
            x[0] = y[0]
            x[1] = y[1]

    str = SegmentTree(n, [n, n], merge_min)
    right = [None] * n
    for i in range(n - 1, -1, -1):
        p = ppp[i]
        right[i] = str.get(p, n)
        str.update(p - 1, [i, n])

    ans = 0
    stl = SegmentTree(n, [-1, -1], merge_max)
    for i in range(n):
        p = ppp[i]
        l1, l2 = stl.get(p, n)
        r1, r2 = right[i]
        ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
        stl.update(p - 1, [i, -1])

    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    """
    値をlistで持つSegmentTree
    update(i, x): i(0-indexed)をxで更新
    get(a,b): [a, b)を取得
    """

    def __init__(self, n, ini, merge):
        self.n = n
        n2 = 1  # nより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [ini[:] for _ in range(n2 << 1)]
        self.ini = ini
        self.merge = merge

    def update(self, i, x):
        i += self.n2
        self.merge(self.tree[i], x)
        while i > 1:
            self.merge(x, self.tree[i ^ 1])
            i >>= 1
            self.tree[i][:] = x

    def get(self, a, b):
        result = self.ini[:]
        self._get(a, b, 1, 0, self.n2, result)
        return result

    def _get(self, a, b, k, l, r, result):
        """
        [a, b)の最小値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での値
        """
        # 範囲外ならINF
        if r <= a or b <= l:
            return
            # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            self.merge(result, self.tree[k])
            return
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        self._get(a, b, k << 1, l, m, result)
        self._get(a, b, (k << 1) + 1, m, r, result)


def solve(n, ppp):
    def merge_min(x, y):
        """ update x """
        if x[0] <= y[0]:
            if x[1] <= y[0]:
                pass
            else:
                x[1] = y[0]
        elif x[0] <= y[1]:
            x[1] = x[0]
            x[0] = y[0]
        else:
            x[:] = y

    def merge_max(x, y):
        """ update x """
        if x[0] >= y[0]:
            if x[1] >= y[0]:
                pass
            else:
                x[1] = y[0]
        elif x[0] >= y[1]:
            x[1] = x[0]
            x[0] = y[0]
        else:
            x[:] = y

    str = SegmentTree(n, [n, n], merge_min)
    right = [None] * n
    for i in range(n - 1, -1, -1):
        p = ppp[i]
        right[i] = str.get(p, n)
        str.update(p - 1, [i, n])

    ans = 0
    stl = SegmentTree(n, [-1, -1], merge_max)
    for i in range(n):
        p = ppp[i]
        l1, l2 = stl.get(p, n)
        r1, r2 = right[i]
        ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
        stl.update(p - 1, [i, -1])

    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    """
    値をlistで持つSegmentTree
    update(i, x): i(0-indexed)をxで更新
    get(a,b): [a, b)を取得
    """

    def __init__(self, n, ini, merge):
        self.n = n
        n2 = 1  # nより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [ini[:] for _ in range(n2 << 1)]
        self.ini = ini
        self.merge = merge

    def update(self, i, x):
        i += self.n2
        self.merge(self.tree[i], x)
        while i > 1:
            self.merge(x, self.tree[i ^ 1])
            i >>= 1
            self.tree[i][:] = x

    def get(self, a, b):
        result = self.ini[:]
        self._get(a, b, 1, 0, self.n2, result)
        return result

    def _get(self, a, b, k, l, r, result):
        """
        [a, b)の最小値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での値
        """
        # 範囲外ならINF
        if r <= a or b <= l:
            return
            # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            self.merge(result, self.tree[k])
            return
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        self._get(a, b, k << 1, l, m, result)
        self._get(a, b, (k << 1) + 1, m, r, result)


def solve(n, ppp):
    def merge_min(x, y):
        """ update x """
        if x[0] <= y[0]:
            if x[1] <= y[0]:
                pass
            else:
                x[1] = y[0]
        elif x[0] <= y[1]:
            x[1] = x[0]
            x[0] = y[0]
        else:
            x[0] = y[0]
            x[1] = y[1]

    def merge_max(x, y):
        """ update x """
        if x[0] >= y[0]:
            if x[1] >= y[0]:
                pass
            else:
                x[1] = y[0]
        elif x[0] >= y[1]:
            x[1] = x[0]
            x[0] = y[0]
        else:
            x[0] = y[0]
            x[1] = y[1]

    str = SegmentTree(n, [n, n], merge_min)
    right = [None] * n
    for i in range(n - 1, -1, -1):
        p = ppp[i]
        right[i] = str.get(p, n)
        str.update(p - 1, [i, n])

    ans = 0
    stl = SegmentTree(n, [-1, -1], merge_max)
    for i in range(n):
        p = ppp[i]
        l1, l2 = stl.get(p, n)
        r1, r2 = right[i]
        ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
        stl.update(p - 1, [i, -1])

    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))

Submission status: Time Limit Exceeded

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

for i in range(N):
    a1 = None
    a2 = None
    b1 = None
    b2 = None
    key = P[i]

    tmp = i
    while tmp > 0:
        tmp -= 1
        if P[tmp] > key:
            if a1 is None:
                a1 = tmp
            else:
                a2 = tmp
                break

    tmp = i
    while tmp < N - 1:
        tmp += 1
        if P[tmp] > key:
            if b1 is None:
                b1 = tmp
            else:
                b2 = tmp
                break

    if a1 is not None:
        _a2 = -1 if a2 is None else a2
        _b1 = N if b1 is None else b1
        s += ((a1 - _a2) * (_b1 - i))*key

    if b1 is not None:
        _b2 = N if b2 is None else b2
        _a1 = -1 if a1 is None else a1
        s += ((_b2 - b1) * (i - _a1))*key

print(str(s))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    """
    値をlistで持つSegmentTree
    update(i, x): i(0-indexed)をxで更新
    get(a,b): [a, b)を取得
    """

    def __init__(self, n, ini, merge):
        self.n = n
        n2 = 1  # nより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [ini[:] for _ in range(n2 << 1)]
        self.ini = ini
        self.merge = merge

    def update(self, i, x):
        i += self.n2
        self.merge(self.tree[i], x)
        while i > 1:
            self.merge(x, self.tree[i ^ 1])
            i >>= 1
            self.tree[i][:] = x

    def get(self, a, b):
        result = self.ini[:]
        self._get(a, b, 1, 0, self.n2, result)
        return result

    def _get(self, a, b, k, l, r, result):
        """
        [a, b)の最小値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での値
        """
        # 範囲外ならINF
        if r <= a or b <= l:
            return
            # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            self.merge(result, self.tree[k])
            return
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        self._get(a, b, k << 1, l, m, result)
        self._get(a, b, (k << 1) + 1, m, r, result)


def solve(n, ppp):
    def merge_min(x, y):
        """ update x """
        if x[0] <= y[0]:
            if x[1] <= y[0]:
                pass
            else:
                x[1] = y[0]
        elif x[0] <= y[1]:
            x[1] = x[0]
            x[0] = y[0]
        else:
            x[0] = y[0]
            x[1] = y[1]

    def merge_max(x, y):
        """ update x """
        if x[0] >= y[0]:
            if x[1] >= y[0]:
                pass
            else:
                x[1] = y[0]
        elif x[0] >= y[1]:
            x[1] = x[0]
            x[0] = y[0]
        else:
            x[0] = y[0]
            x[1] = y[1]

    str = SegmentTree(n, [n, n], merge_min)
    right = []
    for i, p in enumerate(ppp[::-1]):
        i = n - i - 1
        right.append(str.get(p, n))
        str.update(p - 1, [i, n])
    right.reverse()

    ans = 0
    stl = SegmentTree(n, [-1, -1], merge_max)
    for i, p in enumerate(ppp):
        l1, l2 = stl.get(p, n)
        r1, r2 = right[i]
        ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
        stl.update(p - 1, [i, -1])

    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    """
    値をlistで持つSegmentTree
    update(i, x): i(0-indexed)をxで更新
    get(a,b): [a, b)を取得
    """

    def __init__(self, n, ini, merge):
        self.n = n
        n2 = 1  # nより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [ini[:] for _ in range(n2 << 1)]
        self.ini = ini
        self.merge = merge

    def update(self, i, x):
        i += self.n2
        self.merge(self.tree[i], x)
        while i > 1:
            self.merge(x, self.tree[i ^ 1])
            i >>= 1
            self.tree[i][0] = x[0]
            self.tree[i][1] = x[1]

    def get(self, a, b):
        result = self.ini[:]
        self._get(a, b, 1, 0, self.n2, result)
        return result

    def _get(self, a, b, k, l, r, result):
        """
        [a, b)の最小値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での値
        """
        # 範囲外ならINF
        if r <= a or b <= l:
            return
            # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            self.merge(result, self.tree[k])
            return
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        self._get(a, b, k << 1, l, m, result)
        self._get(a, b, (k << 1) + 1, m, r, result)


def solve(n, ppp):
    def merge_min(x, y):
        """ update x """
        if x[0] <= y[0]:
            if x[1] <= y[0]:
                pass
            else:
                x[1] = y[0]
        elif x[0] <= y[1]:
            x[1] = x[0]
            x[0] = y[0]
        else:
            x[0] = y[0]
            x[1] = y[1]

    def merge_max(x, y):
        """ update x """
        if x[0] >= y[0]:
            if x[1] >= y[0]:
                pass
            else:
                x[1] = y[0]
        elif x[0] >= y[1]:
            x[1] = x[0]
            x[0] = y[0]
        else:
            x[0] = y[0]
            x[1] = y[1]

    stl = SegmentTree(n, [-1, -1], merge_max)
    left = []
    for i, p in enumerate(ppp):
        left.append(stl.get(p, n))
        stl.update(p - 1, [i, -1])

    str = SegmentTree(n, [n, n], merge_min)
    right = []
    for i, p in enumerate(ppp[::-1]):
        i = n - i - 1
        right.append(str.get(p, n))
        str.update(p - 1, [i, n])
    right.reverse()
    # print(left)
    # print(right)

    ans = 0
    for i, (l1, l2), (r1, r2) in zip(range(n), left, right):
        ans += ppp[i] * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
P = deque(map(int, input().split()))
s = 0

for i in range(N):
    a1 = None
    a2 = None
    b1 = None
    b2 = None
    key = P[i]

    tmp = i
    while tmp > 0:
        tmp -= 1
        if P[tmp] > key:
            if a1 is None:
                a1 = tmp
            else:
                a2 = tmp
                break

    tmp = i
    while tmp < N - 1:
        tmp += 1
        if P[tmp] > key:
            if b1 is None:
                b1 = tmp
            else:
                b2 = tmp
                break

    if a1 is not None:
        _a2 = -1 if a2 is None else a2
        _b1 = N if b1 is None else b1
        s += ((a1 - _a2) * (_b1 - i))*key

    if b1 is not None:
        _b2 = N if b2 is None else b2
        _a1 = -1 if a1 is None else a1
        s += ((_b2 - b1) * (i - _a1))*key

print(str(s))

Submission status: Time Limit Exceeded

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

for i in range(N):
    a1 = None
    a2 = None
    b1 = None
    b2 = None
    key = P[i]

    tmp = i
    while tmp > 0:
        tmp -= 1
        if P[tmp] > key:
            if a1 is None:
                a1 = tmp
            else:
                a2 = tmp
                break

    tmp = i
    while tmp < N - 1:
        tmp += 1
        if P[tmp] > key:
            if b1 is None:
                b1 = tmp
            else:
                b2 = tmp
                break

    if a1 is not None:
        _a2 = -1 if a2 is None else a2
        _b1 = N if b1 is None else b1
        s += ((a1 - _a2) * (_b1 - i))*key

    if b1 is not None:
        _b2 = N if b2 is None else b2
        _a1 = -1 if a1 is None else a1
        s += ((_b2 - b1) * (i - _a1))*key

print(str(s))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    """
    値をlistで持つSegmentTree
    update(i, x): i(0-indexed)をxで更新
    get(a,b): [a, b)を取得
    """

    def __init__(self, n, ini, merge):
        self.n = n
        n2 = 1  # nより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [ini[:] for _ in range(n2 << 1)]
        self.ini = ini
        self.merge = merge

    def update(self, i, x):
        i += self.n2
        self.tree[i] = self.merge(x, self.tree[i])
        while i > 1:
            self.tree[i >> 1] = x = self.merge(x, self.tree[i ^ 1])
            i >>= 1

    def get(self, a, b):
        return self._get(a, b, 1, 0, self.n2)

    def _get(self, a, b, k, l, r):
        """
        [a, b)の最小値を得る内部関数
        :param k: 現在調べている区間のtree内index
        :param l, r: kが表す区間の左右端index [l, r)
        :return: kが表す区間と[a, b)の共通区間内での値
        """
        # 範囲外ならINF
        if r <= a or b <= l:
            return self.ini
            # [a,b)が完全に[l,r)を包含するならtree[k]の値を採用
        if a <= l and r <= b:
            return self.tree[k]
        # 一部だけ範囲内なら2つに分けて再帰的に調査
        m = (l + r) // 2
        return self.merge(self._get(a, b, k << 1, l, m), self._get(a, b, (k << 1) + 1, m, r))


def solve(n, ppp):
    def merge_min(x, y):
        if x[0] <= y[0]:
            if x[1] <= y[0]:
                return x[:]
            return [x[0], y[0]]
        if x[0] <= y[1]:
            return [y[0], x[0]]
        return y[:]

    def merge_max(x, y):
        if x[0] >= y[0]:
            if x[1] >= y[0]:
                return x[:]
            return [x[0], y[0]]
        if x[0] >= y[1]:
            return [y[0], x[0]]
        return y[:]

    stl = SegmentTree(n, [-1, -1], merge_max)
    left1 = [-1] * n
    left2 = [-1] * n
    for i, p in enumerate(ppp):
        res = stl.get(p, n)
        left1[i] = res[0]
        left2[i] = res[1]
        stl.update(p - 1, [i, -1])

    str = SegmentTree(n, [n, n], merge_min)
    right1 = [n] * n
    right2 = [n] * n
    for i, p in enumerate(ppp[::-1]):
        i = n - i - 1
        res = str.get(p, n)
        right1[i] = res[0]
        right2[i] = res[1]
        str.update(p - 1, [i, n])
    # print(left1)
    # print(left2)
    # print(right1)
    # print(right2)

    ans = 0
    for i, l1, l2, r1, r2 in zip(range(n), left1, left2, right1, right2):
        ans += ppp[i] * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1))
    return ans


n = int(input())
ppp = list(map(int, input().split()))
print(solve(n, ppp))