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


class BTreeNode:
    def __init__(self):
        self.key = []
        self.child = []


class BTree:
    def __init__(self):
        self.root = BTreeNode()

    def search_higher(self, key):
        ptr = self.root
        ret = None
        while ptr.child:
            i = bisect.bisect_right(ptr.key, key)
            if i != len(ptr.key):
                ret = ptr.key[i]
            ptr = ptr.child[i]
        i = bisect.bisect_right(ptr.key, key)
        if i != len(ptr.key):
            ret = ptr.key[i]
        return ret

    def search_lower(self, key):
        ptr = self.root
        ret = None
        while ptr.child:
            i = bisect.bisect_left(ptr.key, key)
            if i != 0:
                ret = ptr.key[i - 1]
            ptr = ptr.child[i]
        i = bisect.bisect_left(ptr.key, key)
        if i != 0:
            ret = ptr.key[i - 1]
        return ret

    def insert(self, key):
        def insert_rec(ptr):
            b_size = 100000
            if not ptr.child:
                bisect.insort(ptr.key, key)
                if len(ptr.key) == b_size * 2 - 1:
                        ret = BTreeNode()
                        ret.key = ptr.key[:b_size]
                        ptr.key = ptr.key[b_size:]
                        return ret
            else:
                i = bisect.bisect(ptr.key, key)
                temp = insert_rec(ptr.child[i])
                if temp is not None:
                    ptr.key.insert(i, temp.key.pop(-1))
                    ptr.child.insert(i, temp)
                    if len(ptr.child) == b_size * 2:
                        ret = BTreeNode()
                        ret.child = ptr.child[:b_size]
                        ptr.child = ptr.child[b_size:]
                        ret.key = ptr.key[:b_size]
                        ptr.key = ptr.key[b_size:]
                        return ret
            return None
        temp = insert_rec(self.root)
        if temp is not None:
            root = BTreeNode()
            root.key = [temp.key.pop(-1)]
            root.child = [temp, self.root]
            self.root = root

    def dump(self):
        def dump_rec(ptr, dep):
            for _ in range(0, dep):
                print("  ", end="")
            print(ptr.key)
            for c in ptr.child:
                dump_rec(c, dep + 1)
        dump_rec(self.root, 0)
        print("")


def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = BTree()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i
#print(ListPos2)
ListPos = [-1, -1] + [ListPos2[n]] + [n, n]
for i in reversed(range(1, n)):
	tempPos = ListPos2[i]
	while (True):
		tempPos += 1
		if (tempPos in ListPos):
			ListPos.insert(ListPos.index(tempPos), ListPos2[i])
			break
	pos = ListPos.index(ListPos2[i])
	low1 = ListPos[pos] - ListPos[pos-1]
	low2 = ListPos[pos-1] - ListPos[pos-2]
	high1 = ListPos[pos+1] - ListPos[pos]
	high2 = ListPos[pos+2] - ListPos[pos+1]
	points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i
#print(ListPos2)
ListPos = [-1, -1] + [ListPos2[n]] + [n, n]
for i in reversed(range(1, n)):
	ListPos = sorted(ListPos + [ListPos2[i]])
	pos = ListPos.index(ListPos2[i])
	low1 = ListPos[pos] - ListPos[pos-1]
	low2 = ListPos[pos-1] - ListPos[pos-2]
	high1 = ListPos[pos+1] - ListPos[pos]
	high2 = ListPos[pos+2] - ListPos[pos+1]
	points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
xx = list(map(int, input().split()))
pp = [(xx[i], i + 1) for i in range(n)]
pp.sort(reverse = True)

larger = [0, 0, pp[0][1], n + 1, n + 1]
ans = 0

for i in range(1, n):
	idx = bisect.bisect_left(larger, pp[i][1])

	ans += (larger[idx - 1] - larger[idx - 2]) * (larger[idx] - pp[i][1]) * pp[i][0]
	ans += (pp[i][1] - larger[idx - 1]	) * (larger[idx + 1] - larger[idx]) * pp[i][0]
	larger.insert(idx, pp[i][1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ListP = [n+1] + [int(i) for i in input().split()] + [n+1]
#ListPos = [ListP.index(i) for i in range(1, n+1)]
points = 0
for i in (range(0, n-1)):
	countHigh1 = 0
	countHigh2 = 0
	countLow1 = 0
	countLow2 = 0
	j = k = l = ListP.index(i+1)
	#print(j)
	while(True):
		j += 1
		if (ListP[j] > i+1):
			countHigh1 = j - l
			break
	while(True):
		if (j == n+1):
			countHigh2 = 0
			break
		j += 1
		if (ListP[j] > i+1):
			countHigh2 = j - (l + countHigh1)
			break
	while(True):		
		k -= 1
		if (ListP[k] > i+1):
			countLow1 = l - k
			break
	while(True):
		if (k == 0):
			break
		k -= 1
		if (ListP[k] > i+1):
			countLow2 = (l - countLow1) - k
			break
	points += (i+1) * (countLow1 * countHigh2 + countHigh1 * countLow2)
	#print(points, countLow1, countHigh2, countHigh1, countLow2)
print(points)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ListP = [n+1] + [int(i) for i in input().split()] + [n+1]
#ListPos = [ListP.index(i) for i in range(1, n+1)]
points = 0
for i in (range(0, n-1)):
	countHigh1 = 0
	countHigh2 = 0
	countLow1 = 0
	countLow2 = 0
	j = k = ListP.index(i+1)
	#print(j)
	while(True):
		countHigh1 += 1
		j += 1
		if (ListP[j] > i+1):
			break
	while(True):
		if (j == n+1):
			break
		countHigh2 += 1
		j += 1
		if (ListP[j] > i+1):
			break
	while(True):
		countLow1 += 1
		k -= 1
		if (ListP[k] > i+1):
			break
	while(True):
		if (k == 0):
			break
		countLow2 += 1
		k -= 1
		if (ListP[k] > i+1):
			break
	points += (i+1) * (countLow1 * countHigh2 + countHigh1 * countLow2)
	#print(points, countLow1, countHigh2, countHigh1, countLow2)
print(points)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ListP = [n+1] + [int(i) for i in input().split()] + [n+1]
ListPos = [ListP.index(i) for i in range(1, n+1)]
points = 0
for i in (range(0, n-1)):
	countHigh1 = 0
	countHigh2 = 0
	countLow1 = 0
	countLow2 = 0
	j = k = ListPos[i]
	#print(j)
	while(True):
		countHigh1 += 1
		j += 1
		if (ListP[j] > i+1):
			break
	while(True):
		if (j == n+1):
			break
		countHigh2 += 1
		j += 1
		if (ListP[j] > i+1):
			break
	while(True):
		countLow1 += 1
		k -= 1
		if (ListP[k] > i+1):
			break
	while(True):
		if (k == 0):
			break
		countLow2 += 1
		k -= 1
		if (ListP[k] > i+1):
			break
	points += (i+1) * (countLow1 * countHigh2 + countHigh1 * countLow2)
	#print(points, countLow1, countHigh2, countHigh1, countLow2)
print(points)

Submission status: Time Limit Exceeded

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

idx = [0] * N
for i in range(N):
    idx[P[i]] = i

ans = 0
for i in range(N - 2, -1, -1):
    find = False
    l1 = idx[i] + 1
    l2 = 0
    for j in range(idx[i] - 1, -1, -1):
        if i < P[j]:
            if not find:
                l1 = idx[i] - j
                l2 = j + 1
                find = True
            else:
                l2 = idx[i] - l1 - j
                break
    
    find = False
    r1 = N - idx[i]
    r2 = 0
    for j in range(idx[i] + 1, N):
        if i < P[j]:
            if not find:
                r1 = j - idx[i]
                r2 = N - j
                find = True
            else:
                r2 = j - r1 - idx[i]
                break
    ans += (i + 1) * (l1 * r2 + l2 * r1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import time
import random


class TreapNode:
    def __init__(self, key, pri):
        self.left = None
        self.right = None
        self.key = key
        self.pri = pri


class Treap:
    def __init__(self):
        self.root = None

    def search_lower(self, key):
        if key == None:
            return None
        ptr = self.root
        ret = None
        while ptr is not None:
            pk = ptr.key
            if pk < key:
                ret = pk
                ptr = ptr.right
            else:
                ptr = ptr.left
        return ret

    def search_higher(self, key):
        if key == None:
            return None
        ptr = self.root
        ret = None
        while ptr is not None:
            pk = ptr.key
            if pk > key:
                ret = pk
                ptr = ptr.left
            else:
                ptr = ptr.right
        return ret

    def insert(self, key):
        pri = random.randrange(0, 2**32)
        ptr = self.root
        elem = TreapNode(key, pri)
        if ptr is None or ptr.pri < pri:
            self.root = elem
        else:
            while True:
                if key < ptr.key:
                    left = ptr.left
                    if left is None or left.pri < pri:
                        ptr.left = elem
                        ptr = left
                        break
                    ptr = left
                else:
                    right = ptr.right
                    if right is None or right.pri < pri:
                        ptr.right = elem
                        ptr = right
                        break
                    ptr = right
        left = elem
        right = elem
        while ptr is not None:
            if key < ptr.key:
                right.left = ptr
                right = ptr
                ptr = ptr.left
            else:
                left.right = ptr
                left = ptr
                ptr = ptr.right
        left.right = None
        right.left = None
        elem.left, elem.right = elem.right, elem.left

# デバッグ用
    def dump(self):
        self.__dump(self.root, 0)

    def __dump(self, idx, dep):
        if idx is not None:
            self.__dump(idx.right, dep + 1)
            for _ in range(0, dep):
                print("   ", end="")
            print([idx.key, idx.pri])
            self.__dump(idx.left, dep + 1)

def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = Treap()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import time
import random


class TreapNode:
    def __init__(self, key, pri):
        self.left = None
        self.right = None
        self.key = key
        self.pri = pri


class Treap:
    def __init__(self):
        self.nil = TreapNode(None, 0)
        self.root = self.nil

    def search_lower(self, key):
        if key == None:
            return None
        ptr = self.root
        ret = None
        nil = self.nil
        while ptr is not nil:
            pk = ptr.key
            if pk < key:
                ret = pk
                ptr = ptr.right
            else:
                ptr = ptr.left
        return ret

    def search_higher(self, key):
        if key == None:
            return None
        ptr = self.root
        ret = None
        nil = self.nil
        while ptr is not nil:
            pk = ptr.key
            if pk > key:
                ret = pk
                ptr = ptr.left
            else:
                ptr = ptr.right
        return ret

    def insert(self, key):
        pri = random.randrange(1, 2**32)
        ptr = self.root
        elem = TreapNode(key, pri)
        if ptr.pri < pri:
            self.root = elem
        else:
            while True:
                if key < ptr.key:
                    left = ptr.left
                    if left.pri < pri:
                        ptr.left = elem
                        ptr = left
                        break
                    ptr = left
                else:
                    right = ptr.right
                    if right.pri < pri:
                        ptr.right = elem
                        ptr = right
                        break
                    ptr = right
        left = elem
        right = elem
        nil = self.nil
        while ptr is not nil:
            if key < ptr.key:
                right.left = ptr
                right = ptr
                ptr = ptr.left
            else:
                left.right = ptr
                left = ptr
                ptr = ptr.right
        left.right = nil
        right.left = nil
        elem.left, elem.right = elem.right, elem.left

# デバッグ用
    def dump(self):
        self.__dump(self.root, 0)

    def __dump(self, idx, dep):
        if idx is not self.nil:
            self.__dump(idx.right, dep + 1)
            for _ in range(0, dep):
                print("   ", end="")
            print([idx.key, idx.pri])
            self.__dump(idx.left, dep + 1)

def main():
    n = int(input())
    p = list(map(int, input().split()))
    idx = [0] * n
    for i in range(0, n):
        idx[i] = i
    idx.sort(key=lambda i: - p[i])
    t = Treap()
    t.insert(-1)
    t.insert(n)
    ans = 0
    for i in idx:
        nex = t.search_higher(i)
        nexnex = t.search_higher(nex)
        pre = t.search_lower(i)
        prepre = t.search_lower(pre)
        if prepre != None:
            ans += p[i] * (pre - prepre) * (nex - i)
        if nexnex != None:
            ans += p[i] * (i - pre) * (nexnex - nex)
        t.insert(i)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int, input().split()))
x = []
ans = 0
for i in range(n-1):
  for j in range(i+1, n):
    x = p[i:j+1]
    x.remove(max(x))
    ans += max(x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
p = [int(i) for i in input().split(" ")]
arg = [0 for i in range(n)]
for i in range(n):
    arg[p[i]-1] = i
arg = np.array(arg)
ind = np.array([-1, -1] + [i for i in range(n)] + [n,n])
co = 0       

mask = np.array([True, True]+[False for i in range(n)]+[True, True])
mask[arg[-1]+2] = True

for i in range(n-2, -1, -1):
    te = arg[i]
    upper = ind[te+3:][mask[te+3:]]
    lower = ind[:te+2][mask[:te+2]]
    s1, s2 = upper[0], upper[1]
    t1, t2 = lower[-1], lower[-2]
    c = (t1-t2)*(s1-te)+(te-t1)*(s2-s1)
    co += c*p[te]
    mask[arg[i]+2] = True
print(co)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
p = [int(i) for i in input().split(" ")]
arg = np.argsort(p)
ind = np.array([-1, -1] + [i for i in range(n)] + [n,n])
co = 0       

mask = np.array([True, True]+[False for i in range(n)]+[True, True])
mask[arg[-1]+2] = True

for i in range(n-2, -1, -1):
    te = arg[i]
    upper = ind[te+3:][mask[te+3:]]
    lower = ind[:te+2][mask[:te+2]]
    s1, s2 = upper[0], upper[1]
    t1, t2 = lower[-1], lower[-2]
    c = (t1-t2)*(s1-te)+(te-t1)*(s2-s1)
    co += c*p[te]
    mask[arg[i]+2] = True
print(co)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
p = [int(i) for i in input().split(" ")]
arg = np.argsort(p)
ind = np.array([-1, -1] + [i for i in range(n)] + [n,n])
co = 0       

mask = np.array([True, True]+[False for i in range(n)]+[True, True])
mask[arg[-1]+2] = True

for i in range(n-2, -1, -1):
    te = arg[i]
    upper = ind[mask][ind[mask] > te]
    lower = ind[mask][ind[mask] < te]
    s1, s2 = upper[0], upper[1]
    t1, t2 = lower[-1], lower[-2]
    c = (t1-t2)*(s1-te)+(te-t1)*(s2-s1)
    co += c*p[te]
    mask[arg[i]+2] = True
print(co)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: -x[0])

    ind_list = [0, 0, num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        # bisect.insort_left(ind_list, ori_ind)
        # add_ind = bisect.bisect_left(ind_list, ori_ind)
        add_ind = bisect.bisect_left(ind_list, ori_ind)
        ind_list.insert(add_ind, ori_ind)
        # print(add_ind)
        l2, l1 = ind_list[add_ind - 2], ind_list[add_ind - 1]
        r2, r1 = ind_list[add_ind + 2], ind_list[add_ind + 1]
        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: -x[0])

    ind_list = [0, 0, num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        # bisect.insort_left(ind_list, ori_ind)
        # add_ind = bisect.bisect_left(ind_list, ori_ind)
        add_ind = bisect.bisect_left(ind_list, ori_ind)
        ind_list.insert(add_ind, ori_ind)
        # print(add_ind)
        l2, l1 = ind_list[add_ind - 2], ind_list[add_ind - 1]
        r2, r1 = ind_list[add_ind + 2], ind_list[add_ind + 1]
        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans += sorted(p[i:j+1], reverse=True)[1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: -x[0])

    ind_list = [0, 0, num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        bisect.insort_left(ind_list, ori_ind)
        add_ind = bisect.bisect_left(ind_list, ori_ind)
        l2, l1 = ind_list[add_ind - 2], ind_list[add_ind - 1]
        r2, r1 = ind_list[add_ind + 2], ind_list[add_ind + 1]
        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
p = list(map(int,input().split()))
q = [(v,i) for i,v in enumerate(p)]
q.sort(reverse=True)
flg = np.array([-1,-1,n,n])
ans = 0

for v,i in q:
    if flg.size==0:
        flg = np.append(flg,i)
        continue
    else:
        flg_arr = np.array(flg)
        flg_low = flg_arr[flg_arr<i]
        flg_upp = flg_arr[flg_arr>i]
        ans += v*(  (flg_low[-1]-flg_low[-2])*(flg_upp[0]-i)+
                    (flg_upp[1]-flg_upp[0])*(i-flg_low[-1]))
        flg = np.append(flg,i)
        flg = np.sort(flg)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
p = list(map(int,input().split()))
q = [(v,i) for i,v in enumerate(p)]
q.sort(reverse=True)
# print(q)
flg = [-1,-1,n,n]
ans = 0

for v,i in q:
    # print("(v,i)=({},{})".format(v,i))
    if not flg:
        flg.append(i)
        # print(flg)
        continue
    else:
        flg_arr = np.array(flg)
        flg_low = flg_arr[flg_arr<i]
        # print("flg_low:{}".format(flg_low))
        flg_upp = flg_arr[flg_arr>i]
        # print("flg_upp:{}".format(flg_upp))

        # if (flg_low.size >= 2) and (flg_upp.size >= 2):
        ans += v*(  (flg_low[-1]-flg_low[-2])*(flg_upp[0]-i)+
                    (flg_upp[1]-flg_upp[0])*(i-flg_low[-1]))
        # elif flg_low.size >= 2 and

        flg = list(flg_arr)
        flg.append(i)
        flg.sort()
        # print(flg)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
s=0
for i in  range(0,n-1):
  for j in range(i+2,n+1):
    x=sorted(p[i:j],reverse=True)
    s=s+x[1]
print(s)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
s=0
for i in  range(0,n-1):
  for j in range(i+2,n+1):
    x=p[i:j]
    x.sort(reverse=True)
    s=s+x[1]
print(s)

Submission status: Time Limit Exceeded

Solution code:
class BIT(object):
    from operator import add
    def __init__(self,A,f=add):
        N=len(A)
        self.__len=N
        self.__f=f
        # built (O(N))
        self.__bit=A[:] # shallow copy
        for i in range(N):
            j=i+((i+1)&-(i+1))
            if j<N: self.tree[j]=self.func(self.tree[i],self.tree[j])

    def __repr__(self):
        return str(self.tree)

    @property
    def func(self):
        return self.__f

    @property
    def tree(self): # getterにしてる意味あんまない
        return self.__bit

    def add(self,i,w):
        while(i<self.__len):
            self.tree[i]=self.func(self.tree[i],w)
            i+=(i+1)&-(i+1)

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

    def bisect_left(self,w):
        # sum(A)より大きければ一番右
        if w>self.sum(self.__len-1): return self.__len
        # 1個しかなく、右じゃないなら左
        elif self.__len==1: return 0
        # それ以外だと、len未満の2のべき乗からスタート
        n=2**((self.__len-1).bit_length()-1)
        res=0
        while(n):
            if res+n-1>self.__len-1: # index over(2べきじゃないときに起こる)
                n//=2
                continue
            if w<=self.tree[res+n-1]: # 左にいく
                n//=2
            else: # 右にいく
                w-=self.tree[res+n-1]
                res+=n
                n//=2
        return res

    def bisect_right(self,w):
        if w>=self.sum(self.__len-1): return self.__len
        elif self.__len==1: return 0
        n=2**((self.__len-1).bit_length()-1)
        res=0
        while(n):
            if w<self.tree[res+n-1]:
                n//=2
            else:
                w-=self.tree[res+n-1]
                res+=n
                n//=2
        return res

# input
n=int(input())
A=list(map(int,input().split()))
# built idx
idx=[0]*n
for i,a in enumerate(A): idx[a-1]=i

# built bit
bit=BIT([0]*n)

# calculate
score=0
for k in range(n,0,-1):
    i=idx[k-1]
    bit.add(i,1)
    s=bit.sum(i)
    # 0.5を引くことでbisect_left=bisect_right
    l0=bit.bisect_left(s-1.5)-(s<=1) # 一番左を含むか含まないかで場合分け
    l1=bit.bisect_left(s-2.5)-(s<=2) # 一番左を含むか含まないかで場合分け
    r0=bit.bisect_left(s+0.5)
    r1=bit.bisect_left(s+1.5)
    score+=k*((l0-l1)*(r0-i)+(r1-r0)*(i-l0))
print(score)

Submission status: Time Limit Exceeded

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

for i in range(1,len(P)):
    max_1 = max(P[i-1],P[i])
    max_2 = min(P[i-1],P[i])
    S += max_2
    for j in range(i-1):
        n = i-j-2
        if P[n] > max_1:
            max_2 = max_1
            max_1 = P[n]
        elif P[n] > max_2:
            max_2 = P[n]
        S += max_2

print(S)

Submission status: Time Limit Exceeded

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

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

ans = 0

for i in range(n):
    label = p[i]
    a = i - 1
    b = i + 1
    count1 = 1
    count2 = 0
    count3 = 1
    count4 = 0
    while a >= 0:
        if label > p[a]:
            a -= 1
            count1 += 1
        else:
            break
    if a >= 0:
        a -= 1
        count2 += 1
    while a >= 0:
        if label > p[a]:
            a -= 1
            count2 += 1
        else:
            break
    while b < n:
        if label > p[b]:
            count3 += 1
            b += 1
        else:
            break
    if b < n:
        b += 1
        count4 += 1
    while b < n:
        if label > p[b]:
            count4 += 1
            b += 1
        else:
            break
    ans += label * (count1 * count4 + count2 * count3)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np

# def second_largest(numbers):
#     count = 0
#     m1 = m2 = float('-inf')
#     for x in numbers:
#         count += 1
#         if x > m2:
#             if x >= m1:
#                 m1, m2 = x, m1            
#             else:
#                 m2 = x
#     return m2 if count >= 2 else None

def second_largest(q):
    q.sort()
    return q[-2]

    

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

cnt = 0
for i in range(len(p)):
    for j in range(i+1,len(p)):
        cnt += second_largest(p[i:j+1])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def second_largest(numbers):
    count = 0
    m1 = m2 = float('-inf')
    for x in numbers:
        count += 1
        if x > m2:
            if x >= m1:
                m1, m2 = x, m1            
            else:
                m2 = x
    return m2 if count >= 2 else None

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

cnt = 0
for i in range(len(p)):
    for j in range(i+1,len(p)):
        cnt += second_largest(p[i:j+1])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
 
P = list(map(int, input().split()))
 
import heapq
my_list = []
sum = 0
for i in range(N-1):
    for j in range(i+1, N):
        my_list = P[i:j+1]
        my_list = [-i for i in my_list]
        heapq.heapify(my_list)
        heapq.heappop(my_list)
        sum += -heapq.heappop(my_list)
 
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=list(map(int,input().split()))
s=0
for i in  range(0,n-1):
  for j in range(i+1,n):
    x=[]
    for k in range(i,j+1):
      x.append(p[k])
    x.sort(reverse=True)
    s=s+x[1]
print(s)