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: Wrong Answer

Solution code:
import itertools
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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


def test(A):
    N = len(A)
    ret = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            b = A[i: j + 1].copy()
            b.sort()
            ret += b[-2]
    return ret


#
# ans = defaultdict(list)
# for a in itertools.permutations(range(1, 5)):
#     t = test(list(a))
#     ans[t].append(a)
#
# for k in sorted(ans.keys()):
#     print('--- {} ---'.format(k))
#     for v in ans[k]:
#         print(v)


# ans = test(P)
# print(ans)


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


def bisect_left_callable(fn, x, lo, hi):
    """
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


def argsort(li):
    return [i for _, i in sorted([(a, i) for i, a in enumerate(li)], reverse=True)]


bit = BinaryIndexedTree(size=N)

idx = argsort(P)
ans = 0
bit.add(idx[0], 1)
for i in idx[1:]:
    cnt = bit.sum(i)
    # cnt が 1 減る場所
    l1 = bisect_left_callable(lambda k: bit.sum(k), cnt, lo=0, hi=i)
    l2 = bisect_left_callable(lambda k: bit.sum(k), cnt - 1, lo=0, hi=i)
    if l1 == 0:
        l1 -= 1
    if l2 == 0:
        l2 -= 1
    # 1 増える場所
    r1 = bisect_left_callable(lambda k: bit.sum(k), cnt + 1, lo=i + 1, hi=N)
    r2 = bisect_left_callable(lambda k: bit.sum(k), cnt + 2, lo=i + 1, hi=N)
    #
    # if cnt != bit.sum(N - 1):
    #     a = (r1 - i) * (l1 - l2)
    # else:
    #     a = 0
    # if cnt > 0:
    #     b = (i - l1 - 1) * (r2 - r1)
    # else:
    #     b = 0

    a = (r1 - i) * (l1 - l2)
    b = max(0, i - l1 - 1) * (r2 - r1)
    # print(P[i], l1, l2, r1, r2, a, b)
    # print(P[i], a + b)
    # rights =

    #ああああああ
    p = i + 1
    ans += p * (a + b)
    bit.add(i, 1)
    # print(lefts)
    # bisect_left_callable()

Submission status: Wrong Answer

Solution code:
N = int(input())
P = list(map(int,input().split()))
L_bigger = [-1 for i in range(N)]
R_bigger = [-1 for i in range(N)]
idx = [0 for i in range(N+1)]
L_max = -1
R_max = -1
for i in range(N):
	p = P[i]
	idx[p] = i
	if L_max < p:
		L_max = p
		continue
	else:
		x = i-1
		while p > P[x]:
			x = L_bigger[x]
		L_bigger[i] = x

for i in range(N):
	p = P[N-1-i]
	if R_max < p:
		R_max = p
		continue
	else:
		x = N-i
		while p > P[x]:
			x = R_bigger[x]
		R_bigger[N-i-1] = x
ans = 0
for i in range(N-1):
	if i == 0:
		ans += (N-1)*(N-1) - N
		continue
	p = i+1
	x = idx[p] + 1
	l = L_bigger[idx[p]] + 1
	r = R_bigger[idx[p]] + 1
	ans += (N+1)*x - (l + r)*x + l*r
print(ans)

Submission status: Wrong Answer

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

for i in range(1,n-1):
    for j in range(i,n):
        if j == i:
            un = P[0:i+1]
            un.sort(reverse=True)
            ma = un[0]
            ni = un[1]
            ans += ni
        else:
            if ma < P[j]:
                ni = ma
                ma = P[j]
                ans += ni
            elif ni < P[j]:
                ni = P[j]
                ans += ni
            else:
                ans += ni
print(ans)

Submission status: Wrong Answer

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

P.sort(reverse=True)
ans = 0
for i in range(1,n):
  ans += P[i]*(n-i)
  
print(ans)

Submission status: Wrong Answer

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

b = [0] * (N + 1)
l1 = [max(i-1,-1) for i in range(N)]
r1 = [min(i+1,N) for i in range(N)]
l2 = [max(i-2,-1) for i in range(N)]
r2 = [min(i+2,N) for i in range(N)]

ans = 0
for i in range(N):
    b[P[i]-1] = i #各数字がaのどこに入っているかをリストbにメモ
for i in range(N):
    m = b[i] #数字がどこに入っているかを探す
    x1,y1,x2,y2 = l1[m] , r1[m] , l2[m] ,r2[m]#その時の左右に動ける大きさをとってくる
    ans += (i+1) * ((x1-x2) * (y1-m+1) + (y1-y2) * (m-x1))#その数が何回使えるかを計算し、答えに追加
    # print(i,x2,x1,y1,y2,m)
    
    #x2
    if x2 >=0:
        r1[x2] = x1
        r2[x2] = y1
    #x1
    if x1 >= 0:
        r1[x1] = y1 
        r2[x1] = y2
    #y1
    if y1 < N:
        l2[y1] = x2 
        l1[y1] = x1    
    #y2
    if y2 < N:
        l2[y2] = x1
        l1[y2] = y1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = list(map(int,input().split()))
def main():
    ans = 0
    left = 0
    while left < N - 1:
        count = 0
        sec = min(P[left],P[left + 1])
        for i in range(left,N):
            count += 1
            if P[i] > sec:
                ans += sec*count
                left += 1
                break
    print(ans)
    return
main()

Submission status: Wrong Answer

Solution code:
# E - Second Sum
N = int(input())
P = list(map(int,input().split()))
tmp = 0
ans = 0

# for i in range(N):
#     for j in range(i+1,N):
#         if j == i + 1:
#             if P[i] > P[j]:
#                 tmp = P[j]
#                 ans += tmp
#             else:
#                 tmp = P[j-1]
#                 ans += tmp
#         else:
#             if tmp > P[j]:
#                 tmp = P[j-1]
#                 ans += tmp
#             else:
#                 tmp = P[j]
#                 ans += tmp
# print(ans)

P.sort(reverse=True)
for i in range(1,N):
    ans += P[i]*i
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = list(map(int, input().split()))
x = 0
for l in range(n - 1):
    for i in range(2, n - l):
        if p[l] <= p[l + 1]:
            first = p[l + 1]
            second = p[l]
        else:
            first = p[l]
            second = p[l + 1]
        if i != 2:
            for k in range(1, i - 1):
                if p[l + k + 1] >= first:
                    second = first
                    first = p[l + k + 1]
                elif p[l + k + 1] > second:
                    second = p[l + k + 1]
            x += second
        else:
            x += second
print(int(x))

Submission status: Wrong Answer

Solution code:
N=int(input())
P=[int(x) for x in input().split()]
score=0
for i in range(N-1):
    score+=(i+1)*(i+1)
print(score)

Submission status: Wrong Answer

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

def s(P, n):
    return (n-1)*P[n]

sum = 0
for i in range(N-1, -1, -1):
    sum += s(P, i)


print(sum+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
p=0
for i in range(n-1):
  p+=a[i]*(n-1-i)
print(p)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# coding: UTF-8

from math import *
import os
import sys

#import scipy.optimize
import numpy as np


##################################################################
if __name__ == "__main__":
    Input = [input() for i in range(2)]
    N = int(Input[0])
    P = list(map(int,Input[1].split()))

    ans = 0
    for L in range(N-1):
        R = N-1
        while R > L:
            A = np.array(P[L:R+1])
            print(A)
            ind = np.where(A==np.sort(A)[-2])
            ind = int(ind[0])
            print(A[ind]*(len(A)-ind))
            if ind == 0:
                ans += A[ind]*(len(A)-ind-1)
                R = 0
            else:
                ans += A[ind]*(len(A)-ind)
                R = L + ind -1
                #sP = sorted(P[L:R+1],reverse=True)
                #ans += sP[1]
    print(ans)

Submission status: Wrong Answer

Solution code:

n = int(input())
P = list(map(int,input().split()))
ans = 0

for i in range(1,n-1):
    for j in range(i,n):
        if j == i:
            un = P[0:i+1]
            un.sort(reverse=True)
            ma = un[0]
            ni = un[1]
            ans += ni
        else:
            if ma < P[j]:
                ni = ma
                ma = P[j]
                ans += ni
            elif ni < P[j]:
                ni = P[j]
                ans += ni
print(ans)

Submission status: Wrong Answer

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

x = [[() for i in range(n)] for j in range(n- 1)]
total = 0

for i in range(n - 1):
  x[i][i + 1] = (min(p[i], p[i + 1]), max(p[i], p[i + 1]))
  total += x[i][i + 1][0]
  
for j in range(1, n - 1):
  for i in range(n - j - 1):
    if x[i][i + j][1] == x[i + 1][i + j + 1][1]:
      x[i][i + j + 1] = (max(x[i][i + j][0], x[i + 1][i + j + 1][0]), x[i][i + j][1])
    elif x[i][i + j][1] == x[i + 1][i + j + 1][0]:
      x[i][ i + j + 1] = x[i + 1][i + j + 1]
    elif x[i][i + j][0] == x[i + 1][i + j + 1][1]:
      x[i][ i + j + 1] = x[i][ i + j]
    else:
      x[i][ i + j + 1] = (min(x[i][i + j][1], x[i + 1][ i + j + 1][1]), max(x[i][i + j][1], x[i + 1][i + j + 1][1]))
    total += x[i][i + j + 1][0]

Submission status: Wrong Answer

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1] 


class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        #left
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        #right
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res

def main():

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

    ST = SegmentTree(P,max,-10**27)

    def bisect(i,j,ST,num,index,P,Smin,Smin_rev,left_flag):
        if left_flag:    
            if i==j:
                if P[i]>num:
                    return i
                else:
                    return i-1
            
            if Smin[j+1]==num:
                return -1
            if P[j]>num:
                return j
        else:
            if i==j:
                if P[i]>num:
                    return i
                else:
                    return i+1
            
            if Smin_rev[i-1]==num:
                return N
            if P[i]>num:
                return i

        if not left_flag:
            while j-i>1:
                if ST.get(index+1,(i+j)//2)<num:
                    i = (i+j)//2
                else:
                    j = (i+j)//2
            return j
        else:
            while j-i>1:
                if ST.get((i+j)//2,index-1)<num:
                    j = (i+j)//2
                else:
                    i = (i+j)//2
            return i

    Smin = []
    smin = -10**27
    for i in range(N):
        smin = max(smin,P[i])
        Smin.append(smin)

    Smin_rev = []
    smin = -10**27
    for i in range(N):
        smin = max(smin,P[N-i-1])
        Smin_rev.append(smin)
    Smin_rev = Smin_rev[::-1]


    score = 0

    for i in range(N):
        if i==0:
            right1 = bisect(i+1,N-1,ST,P[i],i,P,Smin,Smin_rev,False)
            if right1>=N-1:
                right2 = N
            else:
                right2 = bisect(right1+1,N-1,ST,P[i],right1,P,Smin,Smin_rev,False)
            right1,right2 = right1-i,right2-i
            left1 = 1
            left2 = 1
            
        elif i==N-1:
            left1 = bisect(0,i-1,ST,P[i],i,P,Smin,Smin_rev,True)
            if left1<=0:
                left2 = -1
            else:
                left2 = bisect(0,left1-1,ST,P[i],left1,P,Smin,Smin_rev,True)
            left1,left2 = i-left1,i-left2
            right1 = 1
            right2 = 1
        else:
            right1 = bisect(i+1,N-1,ST,P[i],i,P,Smin,Smin_rev,False)
            if right1>=N-1:
                right2 = N
            else:
                right2 = bisect(right1+1,N-1,ST,P[i],right1,P,Smin,Smin_rev,False)
            right1,right2 = right1-i,right2-i

            left1 = bisect(0,i-1,ST,P[i],i,P,Smin,Smin_rev,True)
            if left1<=0:
                left2 = -1
            else:
                left2 = bisect(0,left1-1,ST,P[i],left1,P,Smin,Smin_rev,True)
            left1,left2 = i-left1,i-left2
        
        score += (left1*(right2-right1) + (left2-left1)*right1)*P[i]
    print(score)

main()

Submission status: Wrong Answer

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

Pasc = sorted(P)
cnt = 0
p = N-1

while p>0 and P.index(Pasc[p])<P.index(Pasc[p-1]):
  cnt += 1
  p -= 1

ans = 0

p2 = 0
while p2<N and Pasc[p2]<Pasc[p]:
  ans += Pasc[p2]*(p2+1)
  p2 += 1
  
if cnt>0:
  p2 -= 1
  ans += Pasc[p2]*(cnt+1)
  p2 += 1

  while p2<N-1:
    ans += Pasc[p2]*(p2+1-cnt)
    p2 += 1
    cnt -= 1
    
print(ans)

Submission status: Wrong Answer

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

Pasc = sorted(P)
cnt = 0
p = N-1

while p>0 and P.index(Pasc[p])<P.index(Pasc[p-1]):
  cnt += 1
  p -= 1

ans = 0

p2 = 0
while p2<N and Pasc[p2]<Pasc[p]:
  ans += Pasc[p2]*(p2+1)
  p2 += 1
  
if cnt>0:
  p2 -= 1
  ans += Pasc[p2]*(cnt+1)
  p2 += 1

  while p2<N-1:
    print(p2, ans, Pasc[p2])
    ans += Pasc[p2]*(p2+1-cnt)
    p2 += 1
    cnt -= 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
P = list(map(int, input().split()))
# print(N, P)
ans = 0
l = []
# for i in range(N - 1):
#     bisect.insort(l, P[i])
#     for j in range(i + 1, N):
#         bisect.insort(l, P[j])
#         print(i, j, l[-2], l)
#         ans += l[-2]
#     l = []

bisect.insort(l, P[0])
for i in range(1, N):
    bisect.insort(l, P[i])
    # print(i, j, l[-2], l)
    for j in range(i):
        # print(i, j, l[-2 - j], l)
        ans += l[-2 - j]
print(ans)

Submission status: Wrong Answer

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

from heapq import nlargest
sums = 0

now_max=-10**6
now_add = 0
for i in range(N-1):
    now_max=max(P[i], P[i+1])
    now_add=min(P[i], P[i+1])
    
    for j in range(i+1,N):
        # secondが更新されなければ
        if now_add >= P[j]:
            sums += now_add            
        elif now_max < P[j]:
            now_add = now_max
            now_max = P[j]
            sums += now_add            
        elif now_max > P[j] > now_add:
            now_add=P[j]
            sums += now_add
        else:
            sums += now_add

Submission status: Wrong Answer

Solution code:
num = int(input())
array = list(map(int, input().split()))
sum = 0
top = 0
next = 0
 
for i in range(num-1):
	for j in range(i+1, num, 1):
		for k in range(i, j, 1):
			if k == i:
				top = array[k]
			else:
				if top < array[k]:
					next = top
					top = array[k]
				elif next < array[k]:
					next = array[k]
		sum += next
        
print(sum)

Submission status: Wrong Answer

Solution code:
# E - Second Sum
N = int(input())
P = list(map(int,input().split()))
tmp = 0
ans = 0
P.sort(reverse=True)
for i in range(1,N):
    ans += P[i]*P[i]
print(ans)

Submission status: Wrong Answer

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

from heapq import nlargest
sums = 0

now_mins=10**6
now_add = 0
for i in range(N-1):
    now_max=max(P[i], P[i+1])
    now_add=min(P[i], P[i+1])
    
    for j in range(i+1,N):
        # secondが更新されなければ
        if now_add >= P[j]:
            sums += now_add            
        elif now_max < P[j]:
            now_add = now_max
            now_max = P[j]
            sums += now_add            
        elif now_max > P[j] > now_add:
            now_add=P[j]
            sums += now_add
        else:
            sums += now_add

Submission status: Wrong Answer

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

for i in range(1, n):
    ans += i * i

for i in range(1, n):
    if abs(p[i-1] - p[i]) != 1:
        ans -= 1
if abs(p[0] - p[n-1]) != 1:
        ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    P = list(map(int, input().split()))
    P.sort(reverse=True)
    #print(P)
    ans = 0
    for i in range(N):
        if i == 0:
            pass
        else:
            num = P[i]
            ans += num * (2 ** (N-i) - (N-i))

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# E - Second Sum
N = int(input())
P = list(map(int,input().split()))
tmp = 0
ans = 0

for i in range(N):
    for j in range(i+1,N):
        if j == i + 1:
            if P[i] > P[j]:
                tmp = P[j]
                ans += tmp
            else:
                tmp = P[j-1]
                ans += tmp
        else:
            if tmp > P[j]:
                tmp = P[j-1]
                ans += tmp
            else:
                tmp = P[j]
                ans += tmp
print(ans)

Submission status: Wrong Answer

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

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

print(int(sum(a)/2))

Submission status: Wrong Answer

Solution code:
n = int(input())
p = list(map(int,input().split()))
x = []
count = 0

for i in range(n-1):
    for s in range(n-i):
        if p[i] == p[s+i]:
            continue
        print(p[i],p[s+i])
        x.append(max(p[i],p[s+i])-1)
        print(x)

print(sum(x))

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=LI()

  h=[]
  heapq.heappush(h,-l[0])
  ans=0
  for i,x in enumerate(l[1:]):
    heapq.heappush(h,-x)
    
    _l=[]
    a=heapq.heappop(h)
    _l.append(a)
    for _ in range(i+1):
      a=heapq.heappop(h)
      ans-=a
      _l.append(a)

    for x in _l:
      heapq.heappush(h,x)
  return ans

# main()
print(main())

Submission status: Wrong Answer

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

index_max = P.index(N)
index_2nd = P.index(N-1)

result = 0
for i in range(N-1):
  for j in range(i+2,N+1):
    if index_max >= i and index_max <= j and index_2nd >= i and index_2nd <= j:
      result += N-1
    else:
      result += sorted(P[i:j])[-2]

print(result)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# abc140/abc140_e
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    P = i2nn()
    r = 0
    for L in range(N-1):
        fst = P[L]
        sec = 0
        for R in range(L+1, N):
            p = P[R]
            fst, sec, p = sorted((fst, sec, p))
            r += p
    print(r)
    return

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
P = list(map(int, input().split()))
P.sort(reverse=True)


sum_a = 0
for i in range(1,N-1):
  for j in range(i+1,N+1):
    sum_a += P[i]
  
print(sum_a+P[-1])

Submission status: Wrong Answer

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

#r = 0
#for L in range(N-1):
#  for R in range(L+1, N):
#    r += sorted(Ps[L:R+1])[-2]
#print(r)

Is = [-1]*N
for i in range(N):
  P = Ps[i]
  Is[P-1] = i
r = N*(N-1)*(2*N-1)//6
for i in range(N):
  P = Ps[i]-1
  if i != P:
    Ps[i], Ps[P] = Ps[P], Ps[i]
    if i > P:
      r -= 1
print(r)

Submission status: Wrong Answer

Solution code:
def ruiseki(one,two):
  sorte=sorted(one+[two],reverse=True)
  return [sorte[0],sorte[1]]

N=int(input())
P=[int(i) for i in input().split()]
ans=0
for l in range(N):#左端,Rはl+1からのスタート
  prev=[P[l]]
  max2nd=[]
  for r in range(l+1,N):
    prev=ruiseki(prev,P[r])
    max2nd.append(prev)
  ans+=sum([b for a,b in max2nd])

Submission status: Wrong Answer

Solution code:

class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        #left
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        #right
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res

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

ST = SegmentTree(P,max,-10**27)

def bisect(i,j,ST,num,index,P,Smin,Smin_rev,left_flag):
    if left_flag:    
        if i==j:
            if P[i]>num:
                return i
            else:
                return i-1
        
        if Smin[j+1]==num:
            return -1
        if P[j]>num:
            return j
    else:
        if i==j:
            if P[i]>num:
                return i
            else:
                return i+1
        
        if Smin_rev[i-1]==num:
            return N
        if P[i]>num:
            return i

    if not left_flag:
        while j-i>1:
            if ST.get(index+1,(i+j)//2)<num:
                i = (i+j)//2
            else:
                j = (i+j)//2
        return j
    else:
        while j-i>1:
            if ST.get((i+j)//2,index-1)<num:
                j = (i+j)//2
            else:
                i = (i+j)//2
        return i

Smin = []
smin = -10**27
for i in range(N):
    smin = max(smin,P[i])
    Smin.append(smin)

Smin_rev = []
smin = -10**27
for i in range(N):
    smin = max(smin,P[N-i-1])
    Smin_rev.append(smin)
Smin_rev = Smin_rev[::-1]


score = 0

for i in range(N):
    if i==0:
        right1 = bisect(i+1,N-1,ST,P[i],i,P,Smin,Smin_rev,False)
        if right1>=N-1:
            right2 = N
        else:
            right2 = bisect(right1+1,N-1,ST,P[i],right1,P,Smin,Smin_rev,False)
        right1,right2 = right1-i,right2-i
        left1 = 1
        left2 = 1
        
    elif i==N-1:
        left1 = bisect(0,i-1,ST,P[i],i,P,Smin,Smin_rev,True)
        if left1<=0:
            left2 = -1
        else:
            left2 = bisect(0,left1-1,ST,P[i],left1,P,Smin,Smin_rev,True)
        left1,left2 = i-left1,i-left2
        right1 = 1
        right2 = 1
    else:
        right1 = bisect(i+1,N-1,ST,P[i],i,P,Smin,Smin_rev,False)
        if right1>=N-1:
            right2 = N
        else:
            right2 = bisect(right1+1,N-1,ST,P[i],right1,P,Smin,Smin_rev,False)
        right1,right2 = right1-i,right2-i

        left1 = bisect(0,i-1,ST,P[i],i,P,Smin,Smin_rev,True)
        if left1<=0:
            left2 = -1
        else:
            left2 = bisect(0,left1-1,ST,P[i],left1,P,Smin,Smin_rev,True)
        #print("a",left1,left2)
        left1,left2 = i-left1,i-left2

    score += (left1*(right2-right1) + (left2-left1)*right1)*P[i]
    #print(left1,left2,right1,right2)
print(score)

Submission status: Wrong Answer

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

index = P.index(N-1)

result = 0
for i in range(N-1):
  for j in range(i+2,N+1):
    if index >= i and index <= j:
      result += N-1
    else:
      result += sorted(P[i:j])[-2]

print(result)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
num = int(input())
b = list(map(int, input().split()))
a = []
for i in range(len(b) + 1):
    if i == 0:
        a.append(b[i])
    elif i == len(b):
        a.append(b[len(b)-1])
    else:
        a.append(min(b[i], b[i-1]))
print(sum(a))

Submission status: Wrong Answer

Solution code:
n=int(input())
p=list(map(int,input().split()))
x=0
for i in range(n-1):
    presetmin=min(p[i],p[i+1])
    presetmax=max(p[i],p[i+1])
    x+=presetmin
    for k in range(i+2,n):
        if i+2==n:
            break
        else:
            if p[k]>presetmax:
                x+=presetmax
                presetmax=p[k]
                presetmin=presetmax
            else:
                hoge=max(presetmin,p[k])
                x+=hoge
                if p[k]>presetmin:
                    presetmin=p[k]
print(x)

Submission status: Wrong Answer

Solution code:
n=int(input())
pn=list(map(int,input().split()[:n]))
pn.sort()
k=n-1
print(k*(k+1)*(2*k+1)//6)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
P = list(map(int, input().split()))
p2i = {}
for i, p in enumerate(P):
    p2i[p] = i
# ans = 0
ans = 0
prei = p2i[N]
pred = 0
for p in range(N-1, 2, -1):
    i = p2i[p]
    d = abs(prei-i)-1
    ans += p*(p - d + pred)
    prei = i
    pred = d
# 2
if abs(p2i[2] - p2i[1]) > 2:
    if p2i[2] == 0 or p2i[2] == N-1:
        ans += 2
    else:
        ans += 4
else:
    if p2i[2] == 0 or p2i[2] == N-1 or abs(p2i[2]-p2i[1]) == 1:
        ans += 4
    else:
        ans += 6
    
# 1
if p2i[1] == 0 or p2i[1] == N-1:
    ans += 1
else:
    ans += 2

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ListP = [int(val) for val in input().split()]

l = 0
r = 2
xlr = 0
tempMax = tempMax2 = max2 = 0
while (l < n - 1):
	tempMax2 = min(ListP[l : l + 2])
	xlr += tempMax2
	tempMax = max(ListP[l : l + 2])
	while (r < n):
		if (tempMax2 == max2):
			xlr += (n - 1 - r) * max2
			break
		if (tempMax2 < ListP[r]):
			if (tempMax < ListP[r]):
				tempMax2 = tempMax
				tempMax = ListP[r]
			else:
				tempMax2 = ListP[r]
		xlr += tempMax2
		r += 1
	if (l == 0):
		max2 = tempMax2
	l += 1
	r = l + 2
print(xlr)