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 Nil:
    def __init__(self):
        self.key = 'nil'
        self.color = 'black'
        self.left = None
        self.right = None


class Node:
    def __init__(self, key=None, color='red',
                     parent=None, left=None, right=None):
        self.key = key
        self.color = color
        self.parent = parent
        self.left = left
        self.right = right


class RB:
    def __init__(self):
        self.root = Node(color='black')
        self.root.parent = Nil()
        self.root.parent.left = self.root
        
    def insert(self, key):
        if self.root.key is None:
            self.root.key = key
            return
        
        cursor = self.root
        while cursor:
            if cursor.key == key:
                return
            
            p = cursor
            if key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
                
        new_node = Node(key)
        new_node.parent = p
        if new_node.key < p.key:
            p.left = new_node
            way = 'l'
        else:
            p.right = new_node
            way = 'r'
            
        self.rebalance(p, way)
            
    def rebalance(self, v, dir_vw):
        while v.color == 'red':
            u = v.parent
            if v.key < u.key:
                x = u.right
                if x and x.color == 'red':
                    if u != self.root:
                        u.color = 'red'
                    v.color = 'black'
                    x.color = 'black'
                else:
                    if dir_vw == 'l':
                        self.rotate_r(u, v)
                        return
                    else:
                        self.rotate_lr(u, v)
                        return
            else:
                x = u.left
                if x and x.color == 'red':
                    if u != self.root:
                        u.color = 'red'
                    x.color = 'black'
                    v.color = 'black'
                else:
                    if dir_vw == 'r':
                        self.rotate_l(u, v)
                        return
                    else:
                        self.rotate_rl(u, v)
                        return
            dir_vw = self.get_way(u.parent, u)
            v = u.parent 

    def rotate_r(self, u, v, d=False):
        w = v.left
        v.left = v.right
        v.right = u.right        
        if v.right:
            v.right.parent = v
        
        w.parent = u
        
        u.left = w
        u.right = v
        u.key, v.key = v.key, u.key
        
        if d:
            w.color = 'black'
        
    def rotate_lr(self, u, v, d=False):
        w = v.right
        v.right = w.left
        if v.right:
            v.right.parent = v
        
        w.left = w.right
        w.right = u.right
        if w.right:
            w.right.parent = w
        w.parent = u
        
        u.right = w
        u.key, w.key = w.key, u.key
        
        if d:
            w.color = 'black'
        
    def rotate_l(self, u, v, d=False):
        w = v.right
        
        v.right = v.left
        v.left = u.left
        if v.left:
            v.left.parent = v

        w.parent = u
        
        u.right = w
        u.left = v
        u.key, v.key = v.key, u.key
        
        if d:
            w.color = 'black'
        
    def rotate_rl(self, u, v, d=False):
        w = v.left
        
        v.left = w.right
        if v.left:
            v.left.parent = v
        
        w.right = w.left
        w.left = u.left
        if w.left:
            w.left.parent = w
        w.parent = u
        
        u.left = w
        u.key, w.key = w.key, u.key
        
        if d:
            w.color = 'black'
            
    def get_way(self, u, v):
        if u.left == v:
            return 'l'
        else:
            return 'r'
        
    def find(self, key):
        if self.root.key is None:
            return None
        
        cursor = self.root
        while cursor:
            if cursor.key == key:
                return cursor
            
            if key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        return None
    
        
    def next_smaller_key(self, cursor):
#        cursor = self.find(key)
        if cursor is None:
            return None
        
        if cursor.left:
            cursor = cursor.left
            while cursor.right:
                cursor = cursor.right
            return cursor
        elif cursor.parent.right == cursor:
            return cursor.parent
        elif cursor.parent.left == cursor:
            while cursor.parent.key != 'nil' and cursor.parent.left == cursor:
                cursor = cursor.parent
            if cursor.parent.key != 'nil':
                return cursor.parent
        return None
          
    def next_greater_key(self, cursor):
#        cursor = self.find(key)
        if cursor is None:
            return None
        
        if cursor.right:
            cursor = cursor.right
            while cursor.left:
                cursor = cursor.left
            return cursor
        elif cursor.parent.left == cursor:
            return cursor.parent
        elif cursor.parent.right == cursor:
            while cursor.parent.key != 'nil' and cursor.parent.right == cursor:
                cursor = cursor.parent
            if cursor.parent.key != 'nil':
                return cursor.parent
        return None
    
    def get_smaller_key(self, key):
        cursor = self.find(key)
        l1 = self.next_smaller_key(cursor)
        l2 = self.next_smaller_key(l1)
        if l2 is None:
            l2 = 0
        else:
            l2 = l2.key
        return l1.key, l2
    
    def get_greater_key(self, key):
        cursor = self.find(key)
        r1 = self.next_greater_key(cursor)
        r2 = self.next_greater_key(r1)
        if r2 is None:
            r2 = 0
        else:
            r2 = r2.key
        return r1.key, r2


def main():


    N = int(input())
    P = map(int, input().split())    
    
    idx = [-1] * (N + 1)
    for i, v in enumerate(P, 1):
        idx[v] = i
    avl = RB()
    for i in [0, idx[N], N+1]:
        avl.insert(i)
    total = 0
    
    for j in range(N - 1, 0, -1):
        n = idx[j]
        avl.insert(n)
        
        l1_idx , l2_idx = avl.get_smaller_key(n)
        l1 = n - l1_idx
        if l1_idx != 0:
            l2 = l1_idx - l2_idx
        else:
            l2 = 0
            
        r1_idx, r2_idx = avl.get_greater_key(n)
        r1 = r1_idx - n
        if r1_idx != N + 1:
            r2 = r2_idx - r1_idx
        else:
            r2 = 0
            
        cnt = (l1 * r2 + r1 * l2) * j
        total += cnt
    
    print(total)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-18 00:38:19(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n, *p = [int(x) for x in sys.stdin.read().split()]
    
    ans = 0
    for l in range(n-1):
        if p[l] < p[l+1]:
            largest, second = p[l+1], p[l]
        else:
            largest, second = p[l], p[l+1]
        ans += second
        for r in range(l+2, n):
            if p[r] > largest:
                second, largest = largest, p[r]
            elif p[r] > second:
                second = p[r]
            ans += second
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = [int(x) for x in input().split()]
answer = 0
for i in range(N-1):
  for j in range(i+1,N):
    A=P[i:j+1]
    A.sort()
    answer +=A[-2]
print(answer)

Submission status: Time Limit Exceeded

Solution code:
class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        # self.data = [0] * (self.n + 1)

    def build(self, data):
        pass

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        # self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) >= w
        if w <= 0:
            return 0
        idx = 0  # self.bit[idx] < w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1

    def bisect_right(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) > w
        if w < 0:
            return 0
        idx = 0  # self.bit[idx] <= w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] <= w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


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

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

ans = 0
bit = BIT1(n)
for x in reversed(range(1, n + 1)):
    idx = p2idx[x]
    bit.add(idx, 1)
    idx_rank = bit.sum(idx)
    idx_l2 = bit.bisect_left(idx_rank - 2)
    idx_l1 = bit.bisect_left(idx_rank - 1)
    idx_r1 = bit.bisect_left(idx_rank + 1)
    idx_r2 = bit.bisect_left(idx_rank + 2)

    cnt = 0
    cnt += (idx_l1 - idx_l2) * (idx_r1 - idx)
    cnt += (idx - idx_l1) * (idx_r2 - idx_r1)
    ans += x * cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    from bisect import bisect,insort
    n=int(input())
    p=list(map(int,input().split()))
    p=[0]+p
    q=[0]*(n+1)
    for i in range(1,n+1):
        q[p[i]]=i
    lst=[0,q[n],n+1]
    ans=0
    for i in range(1,n):
        k=i
        i=n-i
        num=q[i]
        a=bisect(lst,num)
        if a==1:
            ans+=i*num*(lst[2]-lst[1])
            insort(lst,num)
        elif a==1+k:
            ans+=i*(n+1-num)*(lst[k]-lst[k-1])
            insort(lst,num)
        else:
            b=lst[a-2]
            c=lst[a-1]
            d=lst[a]
            e=lst[a+1]
            ans+=i*(d-num)*(c-b)+i*(num-c)*(e-d)
            insort(lst,num)
    print(ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def build(self, data):
        pass

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) >= w
        if w <= 0:
            return 0
        idx = 0  # self.bit[idx] < w
        k = 1 << ((self.n).bit_length() - 1)
        while k:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k //= 2
        return idx + 1

    def bisect_right(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) > w
        if w < 0:
            return 0
        idx = 0  # self.bit[idx] <= w
        k = 1 << ((self.n).bit_length() - 1)
        while k:
            if idx + k <= self.n and self.bit[idx + k] <= w:
                w -= self.bit[idx + k]
                idx += k
            k //= 2
        return idx + 1


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

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

ans = 0
bit = BIT1(n)
for x in reversed(range(1, n + 1)):
    idx = p2idx[x]
    bit.add(idx, 1)
    idx_rank = bit.sum(idx)
    idx_l2 = bit.bisect_left(idx_rank - 2)
    idx_l1 = bit.bisect_left(idx_rank - 1)
    idx_r1 = bit.bisect_left(idx_rank + 1)
    idx_r2 = bit.bisect_left(idx_rank + 2)

    cnt = 0
    cnt += (idx_l1 - idx_l2) * (idx_r1 - idx)
    cnt += (idx - idx_l1) * (idx_r2 - idx_r1)
    ans += x * cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def build(self, data):
        pass

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) >= w
        if w <= 0:
            return 0
        idx = 0  # self.bit[idx] < w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1

    def bisect_right(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) > w
        if w < 0:
            return 0
        idx = 0  # self.bit[idx] <= w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] <= w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


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

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

ans = 0
bit = BIT1(n)
for x in reversed(range(1, n + 1)):
    idx = p2idx[x]
    bit.add(idx, 1)
    idx_rank = bit.sum(idx)
    idx_l2 = bit.bisect_left(idx_rank - 2)
    idx_l1 = bit.bisect_left(idx_rank - 1)
    idx_r1 = bit.bisect_left(idx_rank + 1)
    idx_r2 = bit.bisect_left(idx_rank + 2)

    cnt = 0
    cnt += (idx_l1 - idx_l2) * (idx_r1 - idx)
    cnt += (idx - idx_l1) * (idx_r2 - idx_r1)
    ans += x * cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=list(map(int, input().split()))
ans=0
for i in range(N-1):
    max1=max(P[i],P[i+1])
    max2=min(P[i],P[i+1])
    ans+=max2
    for j in range(i+2,N):
        if max1<P[j]:
            max2=max1
            max1=P[j]
            ans+=max2
        elif max2<P[j] and P[j]<max1:
            max2=P[j]
            ans+=max2
        else:
            ans+=max2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    print(n**3)
    return

#B
def B():
    n = II()
    a = LI()
    b = LI()
    c = LI()
    ans = 0
    for i in range(n):
        ans += b[a[i] - 1] + (c[a[i] - 1] if i != n - 1 and a[i] + 1 == a[i + 1] else 0)
    print(ans)
    return

#C
def C():
    n = II()
    b = LI()
    ans = b[0]
    for i in range(n-2):
        if b[i] >= b[i + 1]:
            ans += b[i + 1]
        else:
            ans += b[i]
    print(ans+b[-1])
    return

#D
def D():
    n, k = LI()
    s = S()
    a = []
    for i in range(n):
        if i == n - 1:
            a.append(s[i])
        elif s[i] != s[i + 1]:
            a.append(s[i])
    print(min(n - 1, n - len(a) + 2 * k))
    return

# E
# 解説AC
# Piが何個使えるかというとこまでは良くて
# そのPiよりも大きい数字が左に2個右に2個必要というところまではいけた
# 問題の本質を解決できてはいない
# ここから解説
# 大きい順からみて見たものに対してインデックスを保持
# ここからbisectを使えばlogNでi付近のすでに追加したインデックスを持ってこれる
# あと少しだけどその少しが遠い
def E():
    n = II()
    a = LI()
    d = defaultdict(int)
    for i, ai in enumerate(a):
        d[ai] = i
    lis = [-1, -1, n, n]
    lis.sort()
    num = [i + 1 for i in range(n)][::-1]
    ans = 0
    for i in num:
        l = bisect_left(lis, d[i])
        r = bisect_right(lis, d[i])
        l2 = lis[r - 2]
        l1 = lis[r - 1]
        r1 = lis[l]
        r2 = lis[l + 1]
        ans += i * ((l1 - l2) * (r1 - d[i]) + (d[i] - l1) * (r2 - r1))
        lis.append(d[i])
        lis.sort()
    print(ans)
    return

#F
def F():
    return


#Solve
if __name__ == '__main__':
    E()

Submission status: Time Limit Exceeded

Solution code:
#1から順に見ていく、見た場所を記憶しておく
n = int(input())
l = list(map(int,input().split()))
l2 = [-1] * (n+1)
t=[-1]+list(range(-1,n+1))+[n]
for i,j in enumerate(l):
	l2[j] = i
#場所の記憶
ans  = 0
for i,a in enumerate(l2[1:n],1):
  b=t.index(a)
  L=t[b-1]
  R=t[b+1]
  if L==-1 and R==n:
    break
  elif L==-1:
    R2=t[b+2]
    ans+=i*(R2-R)*(a-L)
  elif R==n:
    L2=t[b-2]
    ans+=i*(L-L2)*(R-a)
  else:
    L2=t[b-2]
    R2=t[b+2]
    ans+=i*((L-L2)*(R-a)+(R2-R)*(a-L))
  t.pop(b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#1から順に見ていく、見た場所を記憶しておく
n = int(input())
l = list(map(int,input().split()))
l2 = [-1] * (n+1)
t=[-1]+list(range(-1,n+1))+[n]
for i,j in enumerate(l):
	l2[j] = i
#場所の記憶
ans  = 0
for i,a in enumerate(l2[1:n],1):
  b=t.index(a)
  ans+=i*((t[b-1]-t[b-2])*(t[b+1]-a)+(t[b+2]-t[b+1])*(a-t[b-1]))
  t.pop(b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#1から順に見ていく、見た場所を記憶しておく
n = int(input())
l = list(map(int,input().split()))
l2 = [-1] * (n+1)
t=[-1]+list(range(-1,n+1))+[n]
for i,j in enumerate(l):
	l2[j] = i
#場所の記憶
ans  = 0
for i in range(n-1):
  a=l2[i+1]
  b=t.index(a)
  ans+=(i+1)*(t[b-1]-t[b-2])*(t[b+1]-a)
  ans+=(i+1)*(t[b+2]-t[b+1])*(a-t[b-1])
  t.pop(b)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N=int(input())
l=list(map(int,input().split()))
l=[-n for n in l]
ans=0
for i in range(1,N):
  for j in range(i+1,N+1):
    la=l[i-1:j]
    heapq.heapify(la)
    a=heapq.heappop(la)
    b=heapq.heappop(la)
    ans+=b
print(-ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = tuple(map(int, input().split()))
first = [[0] * (n+1) for i in range(n)]
second = [[0] * (n+1) for i in range(n)]
for l in range(1, n):
    first[l][l+1] = max(p[l-1], p[l])
    second[l][l+1] = min(p[l-1], p[l])
    for r in range(l+1, n):
        first[l][r+1] = max(
            first[l][r], p[r]
        )
        if second[l][r] <= p[r] <= first[l][r]:
            second[l][r+1] = p[r]
        elif first[l][r] < p[r]:
            second[l][r+1] = first[l][r]
        else:
            second[l][r+1] = second[l][r]
ans = [sum(second[l]) for l in range(1, n)]
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(int, input().split()))
ans = 0
for l in range(N-1):
    first = max(P[l], P[l+1])
    second = min(P[l], P[l+1])
    r = l+2
    ans += second
    while r < N:
        w = P[r]
        r += 1
        if second <= w <= first:
            second = w
        elif first < w:
            second = first
            first = w
        ans += second

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(int, input().split()))
ans = 0
p = []
for l in range(N-1):
    for r in range(l+1, N):
        p = P[l:r+1]
        p.sort(reverse=True)
        ans += p[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
P=list(map(int,input().split()))
ans=0
for l in range(N-1):
    for r in range(l+1,N):
        check=P[l:r+1]
        ans += sorted(check)[-2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def judg(x, dir=False):
    len_x = len(x)+1
    if dir=='left':
        x = x[::-1]
    li = [10**6]*2
    flag = 0
    for ind, i in enumerate(x):
        if flag > 1:
            break
        if i!=0:
            li[flag] = ind+1 #　0 indexed
            flag += 1
    return min(li[0], len_x), min(li[1], len_x)

def main():
    # input
    n = int(input())
    p = list(map(int, input().split()))

    # prepare
    index = [0]*n
    for ind, i in enumerate(p):
        index[n-i] = ind

    # calc
    li = [0]*n
    count = [0]*n
    for i in index:
        r1, r2 = judg(li[i+1:])
        l1, l2 = judg(li[:i], 'left')
        count[i] += l1*(r2-r1)+r1*(l2-l1)
        li[i] = p[i]

    # ans
    ans = 0
    for i in range(n):
        ans += p[i]*count[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans=0
for L in range(N-1):
  for R in range(L+1,N):
    X = P[L:R+1]
    ans += sorted(X)[-2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect,insort
n=int(input())
p=list(map(int,input().split()))
p=[0]+p
q=[0]*(n+1)
for i in range(1,n+1):
    q[p[i]]=i
lst=[0,q[n],n+1]
ans=0
for i in range(1,n):
    k=i
    i=n-i
    num=q[i]
    a=bisect(lst,num)
    if a==1:
        ans+=i*num*(lst[2]-lst[1])
        insort(lst,num)
    elif a==1+k:
        ans+=i*(n+1-num)*(lst[k]-lst[k-1])
        insort(lst,num)
    else:
        b=lst[a-2]
        c=lst[a-1]
        d=lst[a]
        e=lst[a+1]
        ans+=i*(d-num)*(c-b)+i*(num-c)*(e-d)
        insort(lst,num)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
n=int(input())
p=list(map(int,input().split()))
p=[0]+p
q=[0]*(n+1)
for i in range(1,n+1):
    q[p[i]]=i
lst=[0,q[n],n+1]
ans=0
for i in range(1,n):
    k=i
    i=n-i
    num=q[i]
    a=bisect(lst,num)
    if a==1:
        ans+=i*num*(lst[2]-lst[1])
        lst=[0,num]+lst[1:]
    elif a==1+k:
        ans+=i*(n+1-num)*(lst[k]-lst[k-1])
        lst=lst[:1+k]+[num,n+1]
    else:
        b=lst[a-2]
        c=lst[a-1]
        d=lst[a]
        e=lst[a+1]
        ans+=i*(d-num)*(c-b)+i*(num-c)*(e-d)
        lst=lst[:a]+[num]+lst[a:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(int, input().split()))
X = [[0 for i in range(N)] for j in range(N)]
def max_second(li):
    if(len(li) == 1):
        return li[0], li[0]
    l = li[:]
    mxv = max(l)
    l.remove(mxv)
    return mxv, max(l)

for i in range(N-1):
    for j in range(i+1, N):
        first, second = max_second(P[i:j])
        if(first == second):
            X[i][j] = min(first, P[j])
        elif(first < P[j]):
            X[i][j] = first
        elif(first > P[j] and second < P[j]):
            X[i][j] = P[j]
        elif(second > P[j]):
            X[i][j] = second
print(sum([sum(row) for row in X]))

Submission status: Time Limit Exceeded

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):
		ans += sorted(p[l-1:r])[-2]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import insort_left, bisect_left
import sys

input = sys.stdin.readline
N = int(input())
P = map(int, input().split())

idx = [-1] * (N + 1)
for i, v in enumerate(P, 1):
    idx[v] = i
S = [0, idx[N], N+1]
total = 0
for j in range(N - 1, 0, -1):
    n = idx[j]
    i = bisect_left(S, n)
    insort_left(S, n)
    
    l1_idx = S[i-1]
    l1 = n - l1_idx
    if l1_idx != 0:
        l2_idx = S[i-2]
        l2 = l1_idx - l2_idx
    else:
        l2 = 0
        
    r1_idx = S[i+1]
    r1 = r1_idx - n
    if r1_idx != N + 1:
        r2_idx = S[i+2]
        r2 = r2_idx - r1_idx
    else:
        r2 = 0
        
    cnt = (l1 * r2 + r1 * l2) * j
    total += cnt

print(total)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


for i in range(n - 1):
    top = p[i + 1]
    sec = p[i]
    if top < sec:
        top, sec = sec, top
    for j in range(i + 1, n):
        if p[j] > top:
            sec = top
            top = p[j]
           
        else:
            if p[j] < top and p[j] > sec:
                sec = p[j]
        to += sec
    
print(to)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
P = []
for i, p in enumerate(map(int, input().split())):
    P.append([p, i])

P = sorted(P, reverse = True)
    
A = [- 1, - 1, P[0][1], N, N] 

res = 0
for p, i in P[1:]:
    j = bisect.bisect_left(A, i)
    A.insert(j, i)
    res += p*((A[j] - A[j - 1])*(A[j + 2] - A[j + 1]) + (A[j - 1] - A[j - 2])*(A[j + 1] - A[j]))

print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
P_id = [0]*(N + 1)
for i, p in enumerate(map(int, input().split())):
    P_id[p] = i
    
A = [- 1, P_id[N], N] 

res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
P = map(int, input().split())
P_id = [0]*(N + 1)

i = 0
for p in P:
    P_id[p] = i
    i += 1
    
A = [- 1, P_id[N], N] 

res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))
    
print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, - 1, P_id[N], N, N] 

res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l2, l1 = A[j - 2 : j]
    r1, r2 = A[j + 1: j + 3]
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))
    
print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, P_id[N], N] 

res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))
print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, P_id[N], N] 


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    a = A[j]
    l1 = A[j - 1]
    r1 = A[j + 1]
    if l1 != - 1:
        l2 = A[j - 2]
    else:
        l2 = l1
    if r1 != N:
        r2 = A[j + 2]
    else:
        r2 = r1
    
    if l1 == - 1:
        res += i*(a + 1)*(r2 - r1)
    elif r1 == N:
        res += i*(l1 - l2)*(N - a)
    else:
        res += i*((a - l1)*(r2 - r1) + (l1 - l2)*(r1 - a))
print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, P_id[N], N] 


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    if l1 != - 1:
        l2 = A[j - 2]
    else:
        l2 = l1
    if r1 != N:
        r2 = A[j + 2]
    else:
        r2 = r1
    
    if l1 == - 1:
        res += i*(A[j] + 1)*(r2 - r1)
    elif r1 == N:
        res += i*(l1 - l2)*(N - A[j])
    else:
        res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))
print(res)

Submission status: Time Limit Exceeded

Solution code:
def search_index(x, sorted_ls):
    '''
    ソート済み配列からxの入る位置を返す and sorted_lsにxを挿入。
    xの入る位置が複数ある場合は一番左のindexを返す。
    '''
    n = len(sorted_ls)
    l = 0
    r = n
    while l != r:
        a = (r + l)//2
        if x <= sorted_ls[a]:
            r = a
        else:
            l = a + 1
    sorted_ls.insert(l, x)
    return l


N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, P_id[N], N] 


res = 0
for i in range(N - 1, 0, - 1):
    j = search_index(P_id[i], A)
    l1 = A[j - 1]
    r1 = A[j + 1]
    if l1 != - 1:
        l2 = A[j - 2]
    else:
        l2 = l1
    if r1 != N:
        r2 = A[j + 2]
    else:
        r2 = r1
    
    if l1 == - 1:
        res += i*(A[j] + 1)*(r2 - r1)
    elif r1 == N:
        res += i*(l1 - l2)*(N - A[j])
    else:
        res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))
print(res)