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:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
sys.setrecursionlimit(200000)
# local only
# if not __debug__:
#     fin = open('in_1.txt', 'r')
#     sys.stdin = fin
# local only
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

class Avltree:
    """
    AVL木

    Methods
    -------
        search(x: int) -> Union(int)
            ◯.data == x のものが存在するある場合それを出力、ない場合 None を返す
        insert(x: int) -> None
            ◯.data == x がない場合 ◯.data == x なる頂点を作る。ある場合はなにもしない（上書きしない）
        y.to_s() -> int
            頂点yのdataを返す
        y.left_s() -> Union(int, key=None)
            頂点yのleftを返す(ない場合は key)
        search_lower(x: int, key_lower) -> int
            ○.data が x より小さいものの中で最も大きいものを出力、ない場合 key_lower を返す
        search_higher(x:int , key_higher) -> int
            ○.data が x より大きいものの中で最も小さいものを出力、ない場合 key_higher を返す
    """

    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"
    def search(self, key):
        if self.key is None:
            return None
        if self.key > key:
            if self.left is None:
                return None
            else:
                return self.left.search(key)
        if self.key < key:
            if self.right is None:
                return None
            else:
                return self.right.search(key)
        return self  # self.key == keyの場合

    def search_lower(self, key, key_lower):
        if self.key is None:
            return key_lower
        if self.key > key:
            if self.left is None:
                return key_lower
            else:
                return self.left.search_lower(key, key_lower)
        if self.key < key:
            key_lower = self.key
            if self.right is None:
                return key_lower
            else:
                return self.right.search_lower(key, key_lower)
        # self.key == keyの場合
        if self.left is None:
            return key_lower
        else:
            if key_lower is 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 is None:
            return key_higher
        if self.key > key:
            key_higher = self.key
            if self.left is None:
                return key_higher
            else:
                return self.left.search_higher(key, key_higher)
        if self.key < key:
            if self.right is None:
                return key_higher
            else:
                return self.right.search_higher(key, key_higher)
        # self.key == keyの場合
        if self.right is None:
            return key_higher
        else:
            if key_higher is 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 is 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 is 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 is None:  # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left is None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self, key)
        elif key > self.key:
            if self.right is 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 is 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 is 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 is None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right is None:
            return None
        return (self.right).key

def main():
    N = ii()
    P = lmi()
    L = []
    for i in range(N):
        L.append((P[i], i))
    L.sort(key=itemgetter(0), reverse=True)
    # print(L)
    ans = 0
    # rb = Avltree()
    # for x, i in L:
    #     rb.insert(i)
    #     l1 = rb.search_lower(i, -1)
    #     l2 = rb.search_lower(l1, -1)
    #     r1 = rb.search_higher(i, N)
    #     r2 = rb.search_higher(r1, N)
    #     # print(l2, l1, r1, r2)
    #     ans += (abs(i - l1) * abs(r2 - r1) + abs(l1 - l2) * abs(r1 - i)) * x
    print(ans)
    return



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
p = map(int, input().split())
size = math.ceil(math.sqrt(n))
array = []
square = []
for i in range(size ** 2):
    if i < n:
        array.append(p.__next__())
    else:
        array.append(0)
for i in range(size):
    m1, m2 = max(array[i * size], array[i * size + 1]), min(array[i * size], array[i * size + 1])
    for j in range(2, size):
        if m1 < array[i * size + j]:
            m1, m2 = array[i * size + j], m1
        elif m2 < array[i * size + j]:
            m2 = array[i * size + j]
    square.append((m1, m2))
def second(l, r):
    _m1, _m2 = 0, 0
    for i in range(l, l + (-l % size)):
        if _m1 < array[i]:
            _m1, _m2 = array[i], _m1
        elif _m2 < array[i]:
            _m2 = array[i]
    for i in range(math.ceil(l / size), r // size):
        if _m1 < square[i][0]:
            _m1, _m2 = square[i][0], _m1
        elif _m2 < square[i][0]:
            _m2 = square[i][0]
        if _m1 < square[i][1]:
            _m1, _m2 = square[i][1], _m1
        elif _m2 < square[i][1]:
            _m2 = square[i][1]
    for i in range((r // size) * size, r):
        if _m1 < array[i]:
            _m1, _m2 = array[i], _m1
        elif _m2 < array[i]:
            _m2 = array[i]
    return _m2


ans = 0
for i in range(n - 1):
    for j in range(i + 2, n + 1):
        ans += second(i, j)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
p = map(int, input().split())
size = math.ceil(math.sqrt(n))
array = []
square = []
for i in range(size ** 2):
    if i < n:
        array.append(p.__next__())
    else:
        array.append(0)
for i in range(size):
    m1, m2 = max(array[i * size], array[i * size + 1]), min(array[i * size], array[i * size + 1])
    for j in range(2, size):
        if m1 < array[i * size + j]:
            m1, m2 = array[i * size + j], m1
        elif m2 < array[i * size + j]:
            m2 = array[i * size + j]
    square.append((m1, m2))
print(array, square)


def second(l, r):
    _m1, _m2 = 0, 0
    for i in range(l, l + (-l % size)):
        if _m1 < array[i]:
            _m1, _m2 = array[i], _m1
        elif _m2 < array[i]:
            _m2 = array[i]
    for i in range(math.ceil(l / size), r // size):
        if _m1 < square[i][0]:
            _m1, _m2 = square[i][0], _m1
        elif _m2 < square[i][0]:
            _m2 = square[i][0]
        if _m1 < square[i][1]:
            _m1, _m2 = square[i][1], _m1
        elif _m2 < square[i][1]:
            _m2 = square[i][1]
    for i in range((r // size) * size, r):
        if _m1 < array[i]:
            _m1, _m2 = array[i], _m1
        elif _m2 < array[i]:
            _m2 = array[i]
    return _m2


ans = 0
for i in range(n - 1):
    for j in range(i + 2, n + 1):
        ans += second(i, j)
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(N-1):
  m = min(P[i],P[i+1])
  M = max(P[i],P[i+1])  
  for j in range(i+1, N):
#    print (i, j, ":", m, M, P[j], ":",  end =" -> ")
    tm = m
    TM = M
    if j == i+1:
      ans += m
    elif P[j] > TM:
      ans += TM
      M = P[j]
      m = P[j]
    elif P[j] > tm:
      ans += P[j]
      m = P[j]
    else:
      ans += tm
#    print (ans)    
print (ans)

Submission status: Wrong Answer

Solution code:
import bisect
def find_left(P,position):
    N=len(P)
    left1=[-1]*N
    left2=[-1]*N
    stack=[]
    popped=[[] for i in range(len(P))]
    stack=[P[0]]
    for i in range(1,len(P)):
        while stack:
            if stack[-1]<P[i]:
                
                popped[i]+=[stack.pop()]
            else:
                left1[i]=stack[-1]
                stack+=[P[i]]
                
                break
                
        if stack==[]:
            stack+=[P[i]]
            left1[i]=-1
        if left1[i]==-1:
            left2[i]==-1
        else:
            val=left1[i]
            pos=position[val]
            big_val_pos=len(popped[pos])
            if popped[pos]:
                big_val_pos=bisect.bisect_left(popped[pos],P[i])
                if big_val_pos<len(popped[pos]):
                    left2[i]=popped[pos][big_val_pos]
            
            #for x in popped[pos]:
            #    if x>P[i]:
            #        left2[i]=x
            #        break
                    
            
                    
            if left2[i]==-1:
                if len(stack)>=3:
                    left2[i]=stack[-3]
    return left1,left2


def find_right(P,position):
    right1,right2=find_left(P[::-1],position)
    return right1[::-1],right2[::-1]
input()
P=list(map(int,input().strip().split(" ")))



N=len(P)
P=[p-1 for p in P]
position=[0]*len(P)
for i in range(len(P)):
    position[P[i]]=i

left1,left2=find_left(P,position)
right1,right2=find_right(P,position)

for i in range(N):
    if left1[i]!=-1:
        left1[i]=position[left1[i]]
    if left2[i]!=-1:
        left2[i]=position[left2[i]]
    
    if right1[i]==-1:
        right1[i]=N
    else:
        right1[i]=position[right1[i]]
    
    if right2[i]==-1:
        right2[i]=N
    else:
        right2[i]=position[right2[i]]
        
#print(P)
#print(left1,left2)
#print(right1,right2)

ans=0
for i in range(N):
    L1,L2,R1,R2=left1[i],left2[i],right1[i],right2[i]
    val=P[i]+1
    if val==N:
        continue
    temp=0
    if L1==-1:
        temp+=(i+1)*(R2-R1)
    elif R1==N:
        temp+=(L1-L2)*(N-i)
    else:
        temp+=(L1-L2)*(R1-i)
        temp+=(i-L1)*(R2-R1)
    ans+=temp*val
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = sorted(list(map(int, input().split())))
ll = len(li)
ans = 0

for a, l in enumerate(li):
  if a + 1 != ll:
  	ans += (a + 1) * l

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(n):
  z=n
  w=n
  for j in range(i+1,n):
    if p[i]<p[j]:
      z=j
      for k in range(j+1,n):
         if p[i]<p[k]:
            w=k
            break
      break
  x=-1
  y=-1
  for j in range(0,i):
    if p[j]>p[i]:
      y=j
      for k in range(0,j):
         if p[k]>p[i]:
            x=k
            break
      break
  num=(y-x)*(z-i)+(w-z)*(i-y)
  ans+=num*p[i]
print(ans)

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

def shorter(P):
    N = len(P)
    ind2 = np.where(P==np.sort(P)[-2])
    ind1 = np.where(P==np.sort(P)[-1])
    ind2 = int(ind2[0])
    ind1 = int(ind1[0])
    Mind = max(ind1,ind2)
    mind = min(ind1,ind2)
    if Mind < N-1 and mind > 0:
        ans = P[ind2]*(N-Mind)*mind
        return ans,P[mind:Mind+1]
    else:
        return -1,P

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

    ans = 0
    ANS = 0
    while ans>=0:
        ANS += ans
        ans,P = shorter(P)

    N = len(P)
    for L in range(N-1):
        R = N-1
        while R > L:
            A = np.array(P[L:R+1])
            ind2 = np.where(A==np.sort(A)[-2])
            ind1 = np.where(A==np.sort(A)[-1])
            ind2 = int(ind2[0])
            ind1 = int(ind1[0])
            ind = max(ind1,ind2)
            ANS += A[ind2]*(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:
def p_e():
    N = int(input())
    P = list(map(int, input().split()))
    n = N - 1

    ans = n * (n + 1) * (2 * n + 1) // 6

    for i in range(N):
        if not (P[i] == i + 1 or P[i] == N - i):
            ans -= 1

    print(ans)


if __name__ == '__main__':
    p_e()

Submission status: Wrong Answer

Solution code:
N=int(input())
ls=[int(s) for s in input().split()]
count=0
def plus(ls):
  L=len(ls)
  if L>1:
    val_ls=ls
    a=max(val_ls)
    i1=ls.index(a)
    val_ls[i1]=0
    b=max(val_ls)
    i2=ls.index(b)
    val_ls[i1]=a
    i3=max([i1,i2])
    i4=min([i1,i2])
#    print(a,b,i4,i3)
    return [(i4+1)*(L-i3)*b,i4,i3]
  else:
    return 0
S=[ls]
T=[]
ans=0
sign=1
while S!=[]:
  while S!=[]:
    Ls=S[0]
    e=plus(Ls)
    if e==0:
      S.pop(0)
    else:
    #  print(Ls,e)
      ans+=e[0]*sign
      S.pop(0)
      S.append(Ls[:e[2]])
      S.append(Ls[e[1]+1:])
      T.append(Ls[e[1]+1:e[2]])
  S=T
  sign*=-1
#  print(S,T,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
def p_e():
    N = int(input())
    P = list(map(int, input().split()))
    a = 0
    n = N - 1

    ans = n * (n + 1) * (2 * n + 1) // 6

    for i in range(N):
        if P[i] == i + 1 or P[i] == N - i + 1:
            ans -= 1

    print(ans)


if __name__ == '__main__':
    p_e()

Submission status: Wrong Answer

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

class segMax:
  inf = 0
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最大値
    return max(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

class segMin:
  inf = 10 ** 10
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

ans = 0
D = [0] * (N + 1)
for i in range(N):
  D[P[i]] = i + 1

TMa = segMax(N + 1)
TMi = segMin(N + 1)

for i in range(N, 0, -1):
  t = D[i]
  ma = TMa.getV(0, t)
  if ma == 0:
    ma = N + 1
    ma2 = N + 1
  else:
    ma2 = TMa.getV(0, ma - 1)

  mi = TMi.getV(t, N + 1)
  if mi == 10 ** 10:
    mi = 0
    mi2 = 0
  else:
    mi2 = TMi.getV(mi + 1, N + 1)
  
  if ma2 == 0: ma2 = N + 1
  if mi2 == 10 ** 10: mi2 = 0
  TMa.update(t, t)
  TMi.update(t, t)
  if ma == N + 1 and mi == 0:
    continue
  if ma == N + 1:
    if mi2 != 0:
      ans += t * (mi2 - mi) * i
    else:
      ans += t * (mi - t) * i
    continue
  if mi == 0:
    if ma2 != N + 1:
      ans += (N - t + 1) * (ma - ma2) * i
    else:
      ans += (N - t + 1) * (ma) * i
    continue
  if mi2 != 0:
    ans += (mi2 -  mi) * (t - ma) * i
    if ma2 != N + 1:
      ans += (mi - t) * (ma - ma2) * i
    else:
      ans += (mi - t) * ma * i
  else:
    ans += (N - mi + 1) * (t - ma) * i
    if ma2 != N + 1:
      ans += (mi - t) * (ma - ma2) * i
    else:
      ans += (mi - t) * ma * i
      

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

ans = 0

for i in range(N-1):
  for j in range(i+1,N):
    sub = sorted(P[i:j])
    ans += sub[j-i-1]
  
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from heapq import heappush, heappop


def solve(n, sss):
    keys = [-1] + sorted(sss.keys())
    m = keys.pop()
    if sss[m] != 1:
        return False
    k = keys[-1]
    q = [(-n, -m)]
    while k != -1:
        r, s = heappop(q)
        r = -r
        s = -s
        if r == 0:
            continue
        if k >= s:
            tmp = set()
            while q:
                tmp.add((-r, -s))
                r, s = heappop(q)
                r, s = -r, -s
                if k < s:
                    for item in tmp:
                        heappush(q, item)
                    break
            else:
                return False
        heappush(q, (-(r - 1), -k))
        heappush(q, (-(r - 1), -s))
        sss[k] -= 1
        if sss[k] == 0:
            keys.pop()
            k = keys[-1]
        # print(s, r, q, keys, sss)
    return True


n = int(input())
sss = Counter(map(int, input().split()))
print('Yes' if solve(n, sss) else 'No')

Submission status: Wrong Answer

Solution code:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
n=int(input())
p=list(map(int,input().split()))
cnt=0



for i in range(0,n-1):
	c=min(p[i],p[i+1])
	cmax=max(p[i],p[i+1])
	
	for j in range(i+1,n):
		ca=min(c,p[j])
		cb=min(cmax,p[j])
		cnt+=max(ca,cb)

		
print(cnt)

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*(N-1)//2
		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:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
n=int(input())
p=list(map(int,input().split()))
cnt=0



for i in range(0,n-1):
	c=min(p[i],p[i+1])
	cmax=max(p[i],p[i+1])
	
	for j in range(i+1,n):
		ca=min(c,p[j])
		cb=min(cmax,p[j])
		cnt+=max(ca,cb)
		print(max(ca,cb))

		
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
p=list(map(int,input().split()))
c=0
for i in range(n):
    if p[i]!=n:
        a,b=[-1,-1],[n,n]
        t=i+1
        g=0
        while t<n and g!=2:
            if p[i]<p[t]:
                b[g]=t
                g+=1
            t+=1
        t=i-1
        g=0
        while t>-1 and g!=2:
            if p[i]<p[t]:
                b[g]=t
                g+=1
            t-=1
        c+=p[i]*(a[0]*b[1]+a[1]*b[0]-2*a[0]*b[0])
print(c)

Submission status: Wrong Answer

Solution code:

def fs(Q,n):
    l = len(Q) - 1
    res = 0
    for i in range(n + 2):
        res += Q[l - i]
        if res == 2:
            return l - i + 1
def main():
    N = int(input())
    B = list(map(int,input().split()))
    Q = [1] * N
    s = N - 1
    res = N - 1
    for i in range(N - 2):
        Q[i] = 0
        s = fs(Q,i)
        res += s
    s = N - 1
    for i in range(N - 3 ,0,-1):
        Q[i] = 0
        s = fs(Q,i)
        res += s
    print(res)

        
        

if __name__ == "__main__":
    main()

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-2)//2
		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:
#木の根を求める
def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
            size[y] += size[x]
        else:
            par[y] = x
            size[x] += size[y]
            if rank[x]==rank[y]:
                rank[x] += 1

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

########################################
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
	a[i] = -a[i]

par = [0]*n #親
for i in range(n):
    par[i] = i
rank = [1]*n #深さ
size = [1]*n #size[i]:iを根とするグループのサイズ

b = [0]*(n+1) #b[i]:iがaにおいて何番目か
for i in range(n):
    b[-a[i]]=i

ans = 0
for i in range(n,0,-1):
    k = b[i]
    left = 0
    right = 0
    if k-1>=0 and a[k-1]>a[k]:
        left =  size[find(k-1)]
        unite(k-1,k)
    if k+1<=n-1 and a[k+1]>a[k]:
        right = size[find(k+1)]
        unite(k+1,k)
    ans += (left + right+ 2)*(-a[k])

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = list(map(int, input().split()))
index = [[i, X[i]] for i in range(N)]
Xi = list(sorted(index, key=lambda x: x[1], reverse=True))
#print(Xi)
result = 0
for i, j in Xi:
  if N != j:
    #print((N-i-1)*j)
    result += (N-i-1)*j
print(result+N*(N-1)*X[-1]-(N-1))

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N = int(input())
P1 = list(map(int,input().split()))
P2 = sorted(P1)
m1 = P1[-1]
m2 = P2[-2]
a = 0

for i,j in combinations(P1,2):
  l,r = sorted([i,j])
  P3 = P1[l-1:r]
  if m1 in P3 and m2 in P3:
    a+=m2
  else:
    a+=sorted(P3)[-2]

print(a)

Submission status: Wrong Answer

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

class segMax:
  inf = 0
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最大値
    return max(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

class segMin:
  inf = 10 ** 10
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N - 1)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i, L[i])
  def update(s, x, v):
    k = x + s.N - 1
    s.T[k] = v
    while k > 0:
      k = (k - 1) // 2
      s.T[k] = s.do(s.T[2*k+1], s.T[2*k+2])
  def getV(s, l, r):
    return s.getVs(l, r, 0, 0, s.N - 1)
  def getVs(s, l, r, k, kl, kr):
    if l <= kl and r >= kr:
      return s.T[k]
    t = (kl + kr) // 2
    if l > t:
      return s.getVs(l, r, 2 * k + 2, t + 1,kr)
    if r < t + 1:
      return s.getVs(l, r , 2 * k + 1, kl, t)
    return s.do(s.getVs(l, r , 2 * k + 1, kl,t),
              s.getVs(l, r , 2 * k + 2, t + 1, kr))

ans = 0
D = [0] * (N + 1)
for i in range(N):
  D[P[i]] = i + 1

TMa = segMax(N + 1)
TMi = segMin(N + 1)

for i in range(N, 0, -1):
  t = D[i]
  ma = TMa.getV(0, t)
  if ma == 0:
    ma = N + 1
    ma2 = N + 1
  else:
    ma2 = TMa.getV(0, ma - 1)

  mi = TMi.getV(t, N + 1)
  if mi == 10 ** 10:
    mi = 0
    mi2 = 0
  else:
    mi2 = TMi.getV(mi + 1, N + 1)
  
  if ma2 == 0: ma2 = N + 1
  if mi2 == 10 ** 10: mi2 = 0

  TMa.update(t, t)
  TMi.update(t, t)
  if ma == N + 1 and mi == 0:
    continue
  if ma == N + 1:
    if mi2 != 0:
      ans += t * (mi2 - mi) * i
    else:
      ans += t * (mi - t) * i
    continue
  if mi == 0:
    if ma2 != N + 1:
      ans += (N - t + 1) * (ma - ma2) * i
    else:
      ans += (N - t + 1) * (ma) * i
    continue
  if mi2 != 0:
    ans += (mi2 -  mi) * (t - ma) * i
    if ma2 != 0:
      ans += (mi - t) * (ma - ma2) * i
    else:
      ans += (mi - t) * ma * i
  else:
    ans += (N - mi + 1) * (t - ma) * i
    if ma2 != 0:
      ans += (mi - t) * (ma - ma2) * i
    else:
      ans += (mi - t) * ma * i
      

print(ans)

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])
            ind = np.where(A==np.sort(A)[-2])
            ind = int(ind[0])
            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()))
A = [[0]*(N+1)]*(N+1)

total = 0

for j in range(1, N):
  A[2][j] = min(P[j-1], P[j])
  print('i, j _1____' + str(A[2][j]))
  total += A[2][j]

for i in range(3, N+1): #長さiのとき、N-i+1パターン
  for j in range(1, N-i+2):
    if A[i-1][j] != A[i-1][j+1]:
      A[i][j] = max(A[i-1][j],A[i-1][j+1])
      print('i, j _1____' + str(A[i][j]))
    else:
      A[i][j] = min(min(A[i][:j]), max(A[i-1])) + 1
      print('i, j _2____' + str(A[i][j]))
    total += A[i][j]

print(total)