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

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

ans = 0
n = int(input())
p = list(enumerate((map(int,input().split()))))
p.sort(key = lambda x:x[1])
A = Avltree()
while p:
    index,x = p.pop()
    left2 = A.search_lower(index,-1)
    left1 = A.search_lower(left2,-1)
    right1 = A.search_higher(index,n)
    right2 = A.search_higher(right1,n)
    ans += ((left2-left1)*(right1-index)+(right2-right1)*(index-left2))*x
    A.insert(index)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

class BIT:
    """
    1-indexed
    """
    def __init__(self, size):
        self.size = size
        self.data = [0] * (size + 1)

    def add(self, index, value=1):
        while index <= self.size:
            self.data[index] += value
            index += index & (-index)

    def sum(self, index):
        """
        右端含める
        """
        ret = 0
        while index:
            ret += self.data[index]
            index -= index & (-index)
        return ret

    def search(self, val):
        """
        x_1 + ... x_i >= val を満たす最小のi
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)  # 一番上の長さ

        while step:
            if i + step <= self.size and s + self.data[i + step] < val:
                i += step
                s += self.data[i]
            step //= 2
        return i + 1


def sol():
    N = int(input())
    P = [None] + list(map(int, input().split()))

    pToI = {p : i for i, p in enumerate(P[1:], 1)}
    tree = BIT(N)

    ans = 0
    for p in range(1, N + 1)[:: -1]:
        i = pToI[p]
        left = tree.sum(i)  # 左にある個数
        tree.add(i)
        right = (N - p) - left  # 右にある個数(処理済みの内，左にないものの個数)

        # L1 < L2 < p < R1 < R2
        L1 = tree.search(left - 1) if left >= 2 else 0
        L2 = tree.search(left) if left >= 1 else 0
        R1 = tree.search(left + 2) if right >= 1 else N + 1
        R2 = tree.search(left + 3) if right >= 2 else N + 1

        cnt = 0
        if L2 != 0:
            cnt += (L2 - L1) * (R1 - i)
        if R1 != 0:
            cnt += (R2 - R1) * (i - L2)

        ans += cnt * p

    print(ans)

sol()

Submission status: Time Limit Exceeded

Solution code:


INF = 10 ** 6

class SegTree():
    def __init__(self, A):
        n_ = len(A)
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.tree = [INF for _ in range(2 * self.n - 1)]
        for k, a in enumerate(A):
            self.update(k, a)
    def update(self, k, a):
        k += self.n - 1
        self.tree[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])
    def query(self, l, r):
        l += self.n - 1
        r += self.n - 2
        res = INF
        while r-l>1:
            if l&1 == 0:
                res = min(res,self.tree[l])
            if r&1 == 1:
                res = min(res,self.tree[r])
                r -= 1
            l = l//2
            r = (r-1)//2
        if l == r:
            res = min(res,self.tree[l])
        else:
            res = min(min(res,self.tree[l]),self.tree[r])
        return res


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

pii = []

for i, pi in enumerate(p):
    pii.append([pi, i])

pii.sort(reverse=True)

st_r = SegTree([n] * (n+1))
st_l = SegTree([1] * (n+1))

ans = 0

for pi, i in pii:
    # print("###")
    # print(pi, i)
    # print(st_r.tree)
    if pi < n:
        l = -st_l.query(0, i)
        r = st_r.query(i+1, n)
        # print(l, r)
        if l != -1:
            l2 = l - 1
            if l > 0:
                l2 = -st_l.query(0, l)
            ans += (l - l2) * (r - i) * pi
        if r != n:
            r2 = r + 1
            if r < n - 1:
                r2 = st_r.query(r+1, n)
            ans += (i - l) * (r2 - r) * pi

    st_r.update(i, i)
    st_l.update(i, -i)

    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter
from bisect import bisect,insort

def solve(n, ppp):
    q = sorted(enumerate(ppp),key=itemgetter(1),reverse=True)
    le = [-1,-1,q[0][0],n,n]
    ans = 0
    cnt = 3
    for i, p in q[1:]:
        l_i = bisect(le,i,2,cnt)
        LL = le[l_i-2]
        LR = le[l_i-1]
        RL = le[l_i]
        RR = le[l_i+1]
        ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
        insort(le,i)
        cnt += 1
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter
from bisect import bisect,insort

def solve(n, ppp):
    q = sorted(enumerate(ppp),key=itemgetter(1),reverse=True)
    le = [-1,-1,q[0][0],n,n]
    ans = 0
    for i, p in q[1:]:
        l_i = bisect(le,i)
        LL = le[l_i-2]
        LR = le[l_i-1]
        RL = le[l_i]
        RR = le[l_i+1]
        ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
        insort(le,i)
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter
from bisect import bisect,insort
n = int(readline())
ppp = list(map(int,readline().split()))

q = sorted(enumerate(ppp),key=itemgetter(1),reverse=True)
le = [-1,-1,n,n]
ans = 0
for i, p in q:
    l_i = bisect(le,i)
    LL = le[l_i-2]
    LR = le[l_i-1]
    RL = le[l_i]
    RR = le[l_i+1]
    ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
    insort(le,i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter
from bisect import bisect,insort

def solve(n, ppp):
    q = sorted(enumerate(ppp),key=itemgetter(1),reverse=True)
    le = [-1,-1,n,n]
    ans = 0
    for i, p in q:
        l_i = bisect(le,i)
        LL = le[l_i-2]
        LR = le[l_i-1]
        RL = le[l_i]
        RR = le[l_i+1]
        ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
        insort(le,i)
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter
from bisect import bisect,bisect_left,insort

def solve(n, ppp):
    q = sorted(enumerate(ppp),key=itemgetter(1),reverse=True)
    le = [-1,-1,n,n]
    ans = 0
    for i, p in q:
        l_i = bisect(le,i)
        LL = le[l_i-2]
        LR = le[l_i-1]
        RL = le[l_i]
        RR = le[l_i+1]
        ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
        le = le[:l_i]+[i]+le[l_i:]
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter
from bisect import bisect,bisect_left,insort

def solve(n, ppp):
    q = sorted(enumerate(ppp),key=itemgetter(1),reverse=True)
    le = [-1,-1,n,n]
    ans = 0
    for i, p in q:
        l_i = bisect(le,i)
        LL = le[l_i-2]
        LR = le[l_i-1]
        RL = le[l_i]
        RR = le[l_i+1]
        ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
        insort(le,i)
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from bisect import bisect,bisect_left,insort

def solve(n, ppp):
    q = sorted(enumerate(ppp),key=itemgetter(1),reverse=True)
    le = [-1,-1,n,n]
    ans = 0
    for i, p in q:
        l_i = bisect(le,i)
        LL = le[l_i-2]
        LR = le[l_i-1]
        RL = le[l_i]
        RR = le[l_i+1]
        ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
        insort(le,i)
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from bisect import bisect,bisect_left,insort

def solve(n, ppp):
    q = sorted(enumerate(ppp),key=itemgetter(1),reverse=True)
    left = [-1,-1]
    right = [n,n]
    ans = 0
    for i, p in q:
        l_i = bisect(left,i)
        r_i = bisect_left(right,i)
        LL = left[l_i-2]
        LR = left[l_i-1]
        RL = right[r_i]
        RR = right[r_i+1]
        ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
        insort(left,i)
        insort(right,i)
    return ans


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

Submission status: Time Limit Exceeded

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

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans

    data, numPow2 = makeBIT(N)

    iPs = list(range(N))
    iPs.sort(key=lambda iP: Ps[iP])

    ans = 0
    for iP in reversed(iPs):
        v = getSum(iP)
        Bs = []
        for x in range(v-1, v+3):
            if x <= 0:
                L = -1
            elif getSum(numPow2-1) < x:
                L = N
            else:
                maxD = numPow2.bit_length()-1
                L = 0
                S = 0
                for d in reversed(range(maxD)):
                    if S+data[L+(1<<d)] < x:
                        S += data[L+(1<<d)]
                        L += 1<<d
            Bs.append(L)

        num = (Bs[1]-Bs[0])*(Bs[2]-iP) + (iP-Bs[1])*(Bs[3]-Bs[2])
        ans += Ps[iP] * num
        addValue(iP, 1)

    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
P = list(map(int, input().split()))
ind = [0 for _ in range(N+1)]
for i in range(N):
    ind[P[i]] = i+1

lst = [0, 0, N+1, N+1]
ans = 0
for n in range(N, 0, -1):
    pos = bisect.bisect_left(lst, ind[n])
    l1, l2, r1, r2 = lst[pos-2:pos+2]
    ans += n*((l2-l1)*(r1-ind[n]) + (ind[n]-l2)*(r2-r1))
    lst.insert(pos, ind[n])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SparseTable:
    def __init__(self, a, func=max, one=-10**18):
        self.table = [a[:]]
        self.n = len(a)
        self.logn = self.n.bit_length()
        self.func = func
        self.one = one

        for i in map(lambda x: 1 << x, range(self.logn - 1)):
            self.table.append([])
            for j in range(self.n - i * 2 + 1):
                self.table[-1].append(self.func(self.table[-2][j],
                                                self.table[-2][j + i]))

    def get_section(self, i, j):
        length = j - i
        log = length.bit_length() - 1
        if length <= 0:
            return self.one
        return self.func(self.table[log][i], self.table[log][j - length])


def low(m, x):
    mi = 0
    ma = m
    if ma < 0 or sp.get_section(0, ma) <= x:
        return - 1
    while mi != ma:
        mm = (mi + ma) // 2 + 1
        if sp.get_section(mm, m) > x:
            mi = mm
        else:
            ma = mm - 1
    return mi


def high(m, x):
    mi = m + 1
    ma = n - 1
    if m >= n or sp.get_section(m+1, n) <= x:
        return n
    while mi != ma:
        mm = (mi + ma) // 2
        if sp.get_section(m, mm+1) > x:
            ma = mm
        else:
            m1 = mm + 1
    return mi


n = int(input())
p = [int(i) for i in input().split()]

sp = SparseTable(p)

ans = 0
for i in range(n):
    j = low(i, p[i])
    k = low(j, p[i])
    l = high(i, p[i])
    m = high(l, p[i])
    ans += p[i] * ((i-j) * (m-l) + (j-k) * (l-i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    p = list(map(int, input().split()))
    l = []
    for i in range(n):
        l.append([p[i], i])
    l.sort(reverse=True)
    s = [-1, n]
    res = 0
    
    for num, idx in l:
        if len(s) == 2:
            s = [s[0], idx, s[1]]
        else:
            a = bisect_left(s, idx)
            if a == 1:
                res += num * ((s[a+1]-s[a]) * (idx+1))
            elif a== len(s)-1:
                res += num * ((n-idx) * (s[a-1]-s[a-2]))
            else:
                res += num * ((s[a+1]-s[a]) * (idx-s[a-1]) + (s[a]-idx) * (s[a-1]-s[a-2]))
            s.insert(a, idx)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
def solve(P):
    ans = 0
    indices = [0]*N
    for i,p in enumerate(P):
        indices[p-1]=i
    lis = [indices[-1]]
    for i in range(N-2,-1,-1):
        ind = bisect(lis,indices[i])
        if ind > 1:
            l1 = lis[ind-2]
            l2 = lis[ind-1]
        elif ind == 1:
            l1 = -1
            l2 = lis[0]
        else:
            l1 = -1
            l2 = -1
        if ind < len(lis)-1:
            u1 = lis[ind+1]
            u2 = lis[ind]
        elif ind == len(lis)-1:
            u1 = N
            u2 = lis[-1]
        else:
            u1 = N
            u2 = N
        ans += ((u1-u2)*(indices[i]-l2)+(l2-l1)*(u2-indices[i]))*(i+1)
        insort(lis,indices[i])
    return ans
print(solve(P))

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+10)
    def add(self,x,w):
        while x <= self.n:
            self.bit[x] += w
            x += (x&-x)
            
    def sum(self,x):
        cnt = 0
        while x > 0:
            cnt += self.bit[x]
            x -= (x&-x)
        return cnt

    def psum(self,a,b):
        return self.sum(b-1)-self.sum(a-1)

    def bisect(self, w):
        # 値がw以上となる最小のindex
        x = 0
        k = 1
        while k < self.n:
            k *= 2            
        while k > 0:
            # x+kの値がwより小さければ、treeの右側に移動
            if x+k<=self.n and self.bit[x+k] < w:
                w -= self.bit[x+k]
                x += k            
            k //= 2
        return x + 1
    
n = int(input())
ps = list(map(int, input().split()))

# 1-indexedにする
inds = [0]*(n+1)
for i, p in enumerate(ps):
    inds[p] = i+1
bit = BIT(n)
cnt = 0
# 大きい順に
for p in range(n,0,-1):
    ind = inds[p]
    nl = bit.sum(ind)   # 自分より左にあるやつの個数
    nr = (n-p) - nl     # 自分より左にあるやつの個数    
    bit.add(ind, 1)     # bitを1で埋めていく
    # 自分を含んで左右のインデックスを見る(端注意)
    ixl2 = bit.bisect(nl-1) if nl >= 2 else 0
    ixl1 = bit.bisect(nl)   if nl >= 1 else 0
    ixr1 = bit.bisect(nl+2) if nr >= 1 else n+1
    ixr2 = bit.bisect(nl+3) if nr >= 2 else n+1
    tmp = 0
    tmp += (ixl1-ixl2)*(ixr1-ind) #左側から1個取る
    tmp += (ixr2-ixr1)*(ind-ixl1) #右側から1個取る
    cnt += p*tmp    
    # print("p",p,nl,nr,"ind",ixl2,ixl1,ind,ixr1,ixr2,tmp,cnt)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
a = input()
p_list = input().split()
N = len(p_list)
p_list1 = [int(i) for i in p_list]

current_value = 0

for L in range(N - 1):
    first_value = max(p_list1[L], p_list1[L + 1])
    second_value = min(p_list1[L], p_list1[L + 1])
    current_value += second_value
    for R in range(L + 2, N):
        if first_value >= p_list1[R] and second_value <= p_list1[R]:
            second_value = p_list1[R]
        elif first_value < p_list1[R]:
            second_value = first_value
            first_value = p_list1[R]
        

        current_value += second_value

print(current_value)

Submission status: Time Limit Exceeded

Solution code:
a = input()
p_list = input().split()
N = len(p_list)
p_list1 = [int(i) for i in p_list]

current_value = 0

for L in range(N - 1):
    first_value = max(p_list1[L], p_list1[L + 1])
    second_value = min(p_list1[L], p_list1[L + 1])
    current_value += second_value
    for R in range(L + 2, N):
        if first_value < p_list1[R]:
            second_value = first_value
            first_value = p_list1[R]
        elif first_value >= p_list1[R] and second_value <= p_list1[R]:
            second_value = p_list1[R]

        current_value += second_value

print(current_value)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=list(map(int,input().split()))
ans=0
a_max=0
for i in range(N-1):
    a_max=P[i]
    pre=0
    for j in range(i+1,N):
        if a_max>P[j]:
            if pre>P[j]:
                ans+=pre
            else:
                ans+=P[j]
                pre=P[j]
        else:
            ans+=a_max
            pre=a_max
            a_max=P[j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = input()
p_list = input().split()
N = len(p_list)
p_list1 = []
for item in p_list:
    p_list1.append(int(item))
current_value = 0

for L in range(N - 1):

    for R in range(L + 1, N):
        if R == L + 1:
            first_value = max(p_list1[L], p_list1[R])
            second_value = min(p_list1[L], p_list1[R])

        else:
            if first_value < p_list1[R]:
                second_value = first_value
                first_value = p_list1[R]

            elif first_value >= p_list1[R] and second_value <= p_list1[R]:
                second_value = p_list1[R]


        
        current_value += second_value

print(current_value)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = [(int(x), i) for i, x in enumerate(input().split())]
p.sort(reverse=True)

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (self.n+1)
    
    def sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res
    
    def add(self, i, x):
        if i <= 0: return
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    def lower_bound(self, x):
        if x <= 0: return 0
        cur, s, k = 0, 0, 1 << (self.n.bit_length()-1)
        while k:
            nxt = cur + k 
            if nxt <= self.n and s + self.data[nxt] < x:
                s += self.data[nxt]
                cur = nxt
            k >>= 1
        return cur + 1

bit = BinaryIndexedTree(n)
ans = 0

for x, i in p:
    i += 1
    bit.add(i, 1)
    idx = bit.sum(i)
    l1, l2 = bit.lower_bound(idx-1), bit.lower_bound(idx-2)
    r1, r2 = bit.lower_bound(idx+1), bit.lower_bound(idx+2)
    ans += ((l1-l2) * (r1-i) + (i-l1) * (r2-r1)) * x

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
p = list(map(int, input().split()))
pi = sorted(zip(p, range(n)))

index = [-1, -1, pi[n - 1][1], n, n]
ret = 0
for pos in range(n - 2, -1, -1):
    p, i = pi[pos]
    ii = bisect.bisect_left(index, i)
    ret += p * (index[ii - 1] - index[ii - 2]) * (index[ii] - i)
    ret += p * (i - index[ii - 1]) * (index[ii + 1] - index[ii])
    bisect.insort_left(index, i)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
p = list(map(int, input().split()))
pi = sorted(zip(p, range(n)))

index = [-1, -1, pi[n - 1][1], n, n]
ret = 0
for pos in range(n - 2, -1, -1):
    p, i = pi[pos]
    ii = bisect.bisect_left(index, i)
    ret += p * (index[ii - 1] - index[ii - 2]) * (index[ii] - i)
    ret += p * (i - index[ii - 1]) * (index[ii + 1] - index[ii])
    index.insert(ii, i)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    class Bit():
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)
            return

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x=1):
            # i==0 はだめ => 全部+1するとか
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def search(self, x):
            # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
            # maspyさんの参考
            i = 0
            s = 0
            step = 1 << ((self.size).bit_length() - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < x:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return i + 1

        def debug(self, k):
            return [self.sum(i) for i in range(k)]

    N = I()
    P = LI()
    Order = [[i+1] for i in range(N)]
    for i,p in enumerate(P):
        Order[i].append(p)
    Order.sort(key=lambda x:x[1],reverse=True)
    #print(Order)
    ans = 0
    bit = Bit(N+2)

    for i,p in Order:
        L = bit.sum(i)
        R = bit.sum(N)-L
        bit.add(i)
        l0, l1, r0, r1 = 0, 0, N+1, N+1
        if L>=2:
            l0 = bit.search(L-1)
        if L>=1:
            l1 = bit.search(L)
        if R>=1:
            r0 = bit.search(L+2)
        if R>=2:
            r1 = bit.search(L+3)
        #print(L,R)
        #print(l0,l1,r0,r1)
        #print(bit.debug(N+2))
        cnt = 0
        if l1>0:
            cnt += (l1-l0)*(r0-i)
        if r0>0:
            cnt += (i-l1)*(r1-r0)
        ans += cnt * p
        #print(ans)
    print(ans)
    return

def examF():
    def bfs(n, e, S):
        W = [0]*(2**n)
        cur = 1
        que = deque()
        que.append(e)
        while cur<2**n:
            now = que.popleft()
            depth = W[now]
            if S[now]<=S[cur]:
                return "No"
            for ne in range(n-depth):
                cur +=1
                W[now+1+ne] = depth+1
                que.append(now+1+ne)
        return "Yes"
    N = I()
    S = LI(); S.sort(reverse=True)
    ans = bfs(N,0,S)
    print(ans)
    return


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""