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:
n,ans,sum=int(input()),0,0
P=list(map(int,input().split()))
first,second=P[n-1],P[n-1]
first_pos,second_pos = n-1,n-1
li = 0
count = 1

for i in range(n-2,-1,-1):
  x = P[i]
  if x > first:
    second = first
    first = x
    second_pos = first_pos
    first_pos = i
    sum = li + (n - second_pos) * second
    li = 0
    
  elif second < x and x < first:
    second,second_pos = x,i
    sum = second * (n - i -1)
    count += 1
    li += x
    
  else:
    sum += x
    count += 1
    li += x
    
  ans += sum
  
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

P = [None for i in range(N)]
for i in range(N):
  P[A[i]-1] = i

R = DD(lambda:N)
L = DD(lambda:-1)
R2 = DD(lambda:N)
L2 = DD(lambda:-1)

stack = []
stack2 = deque([])
for i in range(N):
  while stack2 and stack2[-1]<A[i]:
    R2[stack2.pop()-1] = i
  while stack and stack[-1]<A[i]:
    a = stack.pop()
    R[a-1] = i
    stack2.appendleft(a)
  stack.append(A[i])
  
stack = []
stack2 = deque([])
for i in range(N)[::-1]:
  while stack2 and stack2[-1]<A[i]:
    L2[stack2.pop()-1] = i
  while stack and stack[-1]<A[i]:
    a = stack.pop()
    L[a-1] = i
    stack2.appendleft(a)
  stack.append(A[i])

ans = 0
for i in range(N):
  a,b,c,d,e = L2[i],L[i],P[i],R[i],R2[i]
  ans += ((c-b)*(e-d) + (b-a)*(d-c))*(i+1)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

P = [None for i in range(N)]
for i in range(N):
  P[A[i]-1] = i

R = DD(lambda:N)
L = DD(lambda:-1)
R2 = DD(lambda:N)
L2 = DD(lambda:-1)

stack = []
stack2 = []
for i in range(N):
  while stack2 and stack2[-1]<A[i]:
    R2[stack2.pop()-1] = i
  while stack and stack[-1]<A[i]:
    a = stack.pop()
    R[a-1] = i
    stack2.append(a)
  stack.append(A[i])

stack = []
stack2 = []
for i in range(N)[::-1]:
  while stack2 and stack2[-1]<A[i]:
    L2[stack2.pop()-1] = i
  while stack and stack[-1]<A[i]:
    a = stack.pop()
    L[a-1] = i
    stack2.append(a)
  stack.append(A[i])
      
ans = 0
for i in range(N):
  a,b,c,d,e = L2[i],L[i],P[i],R[i],R2[i]
  ans += ((c-b)*(e-d) + (b-a)*(d-c))*(i+1)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dic={}
for i in range(n):
    dic[p[i]]=i
# print(dic)

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    # [1,i]の足し算
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    # [i,j]の足し算
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i-1)

bi=BIT(n+1)
ans=0
for i in range(n)[::-1]:
    bi.add(dic[i+1]+1,i+1)
    # print(bi.el)
    lsum=bi.get(1,dic[i+1])
    l,r=-1,dic[i+1]
    while r-l>1:
        half=(r+l)//2
        if bi.get(1,half)>=lsum:
            r=half
        else:
            l=half
    l1=r
    l2=-1
    if r!=0:
        lsum=bi.get(1,r-1)
        l,r=-1,r-1
        while r-l>1:
            half=(r+l)//2
            if bi.get(1,half)>=lsum:
                r=half
            else:
                l=half
        l2=r
    # print(l1,l2)
    rsum=bi.get(dic[i+1]+2,n)
    l,r=dic[i+1]+1,n+1
    while r-l>1:
        half=(r+l)//2
        if bi.get(half,n)>=rsum:
            l=half
        else:
            r=half
    # print(rsum,l,r)
    r1=l
    r2=n+1
    if r!=n+1:
        rsum=bi.get(r1+1,n)
        l,r=r1+1,n+2
        while r-l>1:
            half=(r+l)//2
            if bi.get(half,n)>=rsum:
                l=half
            else:
                r=half
        r2=l
    # print(l1,l2)
    # print(r1,r2)
    # print(bi.el)
    if i==n-1:
        continue
    if l1==0:
        ans+=(dic[i+1]+1)*(r2-r1)*(i+1)
    elif r1==n:
        ans+=(n-dic[i+1])*(l1-l2)*(i+1)
    else:
        ans+=((r2-r1)*(dic[i+1]+1)+(n-dic[i+1])*(l1-l2))*(i+1)
    # ans+=((dic[i+1]-l1)*(r2-r1)+(l1-l2)*(r1-dic[i+1]))*(i+1)
    # print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

class OrderedSet:
    def __init__(self,a):
        self.c = {}
        self.r = {}
        self.a_sort = sorted(list(set(a)))
        for i,a in enumerate(self.a_sort):
            self.c[a] = i+1
            self.r[i+1] = a
        self.size = len(self.c)
        self.tree = [0]*(self.size + 1)
        self.num = [0]*self.size
        self.all_count = 0  # 全要素数

    # BITのsum関数
    def _sum(self,index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s

    # xをk個挿入する
    def insert(self,x,k=1):
        index = self.c[x]
        self.num[index-1] += k
        while index <= self.size:
            self.tree[index] += k
            index += index & (-index)
        self.all_count += k
    
    # xをk個削除する
    def erase(self,x,k=1):
        self.insert(x,k=-k)

    # 格納しているxの数を返す
    def count(self,x):
        return self.num[self.c[x]-1]

    # 下から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_bottom(self,k):
        if k <= 0:
            return None
        elif self.all_count < k:
            return None
        else:
            i = 0
            s = 0
            step = 1 << (self.size.bit_length() - 1)
            while step:
                if i+step <= self.size and s+self.tree[i+step] < k:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return self.r[i+1]
    
    # 上から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_top(self,k):
        return self.get_kth_bottom(self.all_count-k+1)
    
    # x以上の最小要素を返す
    def lower_bound(self,x):
        p = bisect_left(self.a_sort,x)
        if p == 0:
            k = 1
        else:
            k = self._sum(p) + 1
        return self.get_kth_bottom(k)
    
    # x以下の最大要素を返す
    def upper_bound(self,x):
        p = bisect_right(self.a_sort,x)
        if p == 0:
            return None
        else:
            k = self._sum(p)
            return self.get_kth_bottom(k)

N = I()
P = LI()

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

s = OrderedSet(P)
ans = 0
for i in range(1,N+1)[::-1]:
    p = places[i]
    c = s.lower_bound(p)
    d = None if c is None else s.lower_bound(c+1)
    b = s.upper_bound(p)
    a = None if b is None else s.upper_bound(b-1)
    
    a = a if a is not None else 0
    d = d if d is not None else N+1

    if b is None:
        if c is not None:
            ans += i*p*(d-c)
    elif c is None:
        ans += i*(b-a)*(N-p+1)
    else:
        ans += i*((b-a)*(c-p)+(p-b)*(d-c))

    s.insert(p)

print(ans)

print('時間計測')

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

class OrderedSet:
    def __init__(self,a):
        self.c = {}
        self.r = {}
        self.a_sort = sorted(list(set(a)))
        for i,a in enumerate(self.a_sort):
            self.c[a] = i+1
            self.r[i+1] = a
        self.size = len(self.c)
        self.tree = [0]*(self.size + 1)
        self.num = [0]*self.size
        self.all_count = 0  # 全要素数

    # BITのsum関数
    def _sum(self,index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s

    # xをk個挿入する
    def insert(self,x,k=1):
        index = self.c[x]
        self.num[index-1] += k
        while index <= self.size:
            self.tree[index] += k
            index += index & (-index)
        self.all_count += k
    
    # xをk個削除する
    def erase(self,x,k=1):
        self.insert(x,k=-k)

    # 格納しているxの数を返す
    def count(self,x):
        return self.num[self.c[x]-1]

    # 下から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_bottom(self,k):
        if k <= 0:
            return None
        elif self.all_count < k:
            return None
        else:
            i = 0
            s = 0
            step = 1 << (self.size.bit_length() - 1)
            while step:
                if i+step <= self.size and s+self.tree[i+step] < k:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return self.r[i+1]
    
    # 上から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_top(self,k):
        return self.get_kth_bottom(self.all_count-k+1)
    
    # x以上の最小要素を返す
    def lower_bound(self,x):
        if x in self.c.keys():
            p = self.c[x]-1
        else:
            p = bisect_left(self.a_sort,x)
        if p == 0:
            k = 1
        else:
            k = self._sum(p) + 1
        return self.get_kth_bottom(k)
    
    # x以下の最大要素を返す
    def upper_bound(self,x):
        if x in self.c.keys():
            p = self.c[x]
        else:
            p = bisect_right(self.a_sort,x)
        if p == 0:
            return None
        else:
            k = self._sum(p)
            return self.get_kth_bottom(k)

N = I()
P = LI()

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

s = OrderedSet(P)
ans = 0
for i in range(1,N+1)[::-1]:
    p = places[i]
    c = s.lower_bound(p)
    d = None if c is None else s.lower_bound(c+1)
    b = s.upper_bound(p)
    a = None if b is None else s.upper_bound(b-1)
    
    a = a if a is not None else 0
    d = d if d is not None else N+1

    if b is None:
        if c is not None:
            ans += i*p*(d-c)
    elif c is None:
        ans += i*(b-a)*(N-p+1)
    else:
        ans += i*((b-a)*(c-p)+(p-b)*(d-c))

    s.insert(p)

print(ans)

print('時間計測')

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

class OrderedSet:
    def __init__(self,a):
        self.c = {}
        self.r = {}
        self.a_sort = sorted(list(set(a)))
        for i,a in enumerate(self.a_sort):
            self.c[a] = i+1
            self.r[i+1] = a
        self.size = len(self.c)
        self.tree = [0]*(self.size + 1)
        self.num = [0]*self.size
        self.all_count = 0  # 全要素数

    # BITのsum関数
    def _sum(self,index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s

    # xをk個挿入する
    def insert(self,x,k=1):
        index = self.c[x]
        self.num[index-1] += k
        while index <= self.size:
            self.tree[index] += k
            index += index & (-index)
        self.all_count += k
    
    # xをk個削除する
    def erase(self,x,k=1):
        self.insert(x,k=-k)

    # 格納しているxの数を返す
    def count(self,x):
        return self.num[self.c[x]-1]

    # 下から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_bottom(self,k):
        if k <= 0:
            return None
        elif self.all_count < k:
            return None
        else:
            i = 0
            s = 0
            step = 1 << (self.size.bit_length() - 1)
            while step:
                if i+step <= self.size and s+self.tree[i+step] < k:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return self.r[i+1]
    
    # 上から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_top(self,k):
        return self.get_kth_bottom(self.all_count-k+1)
    
    # x以上の最小要素を返す
    def lower_bound(self,x):
        #p = bisect_left(self.a_sort,x)
        p = self.size//2
        if p == 0:
            k = 1
        else:
            k = self._sum(p) + 1
        return self.get_kth_bottom(k)
    
    # x以下の最大要素を返す
    def upper_bound(self,x):
        #p = bisect_right(self.a_sort,x)
        p = self.size//2
        if p == 0:
            return None
        else:
            k = self._sum(p)
            return self.get_kth_bottom(k)

N = I()
P = LI()

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

s = OrderedSet(P)
ans = 0
for i in range(1,N+1)[::-1]:
    p = places[i]
    c = s.lower_bound(p)
    d = None if c is None else s.lower_bound(c+1)
    b = s.upper_bound(p)
    a = None if b is None else s.upper_bound(b-1)
    
    a = a if a is not None else 0
    d = d if d is not None else N+1

    if b is None:
        if c is not None:
            ans += i*p*(d-c)
    elif c is None:
        ans += i*(b-a)*(N-p+1)
    else:
        ans += i*((b-a)*(c-p)+(p-b)*(d-c))

    s.insert(p)

print(ans)

print('時間計測')

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

class OrderedSet:
    def __init__(self,a):
        self.c = {}
        self.a_sort = sorted(list(set(a)))
        for i,a in enumerate(self.a_sort):
            self.c[a] = i + 1
        self.r = {v: k for k, v in self.c.items()}
        self.size = len(self.c)
        self.tree = [0]*(self.size + 1)
        #self.num = [0]*self.size
        self.all_count = 0  # 全要素数

    # BITのsum関数
    def _sum(self,index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s

    # xをk個挿入する
    def insert(self,x,k=1):
        index = self.c[x]
        #self.num[index-1] += k
        while index <= self.size:
            self.tree[index] += k
            index += index & (-index)
        self.all_count += k
    
    # xをk個削除する
    def erase(self,x,k=1):
        self.insert(x,k=-k)

    # 格納しているxの数を返す
    #def count(self,x):
    #    return self.num[self.c[x]-1]

    # 下から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_bottom(self,k):
        if k <= 0:
            return None
        elif self.all_count < k:
            return None
        else:
            i = 0
            s = 0
            step = 1 << (self.size.bit_length() - 1)
            while step:
                if i+step <= self.size and s+self.tree[i+step] < k:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return self.r[i+1]
    
    # 上から数えてk番目の要素を返す（要素がk個未満のときNoneを返す）
    def get_kth_top(self,k):
        return self.get_kth_bottom(self.all_count-k+1)
    
    # x以上の最小要素を返す
    def lower_bound(self,x):
        p = bisect_left(self.a_sort,x)
        if p == 0:
            k = 1
        else:
            k = self._sum(p) + 1
        return self.get_kth_bottom(k)
    
    # x以下の最大要素を返す
    def upper_bound(self,x):
        p = bisect_right(self.a_sort,x)
        if p == 0:
            return None
        else:
            k = self._sum(p)
            return self.get_kth_bottom(k)

N = I()
P = LI()

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

s = OrderedSet(P)
ans = 0
for i in range(1,N+1)[::-1]:
    p = places[i]
    c = s.lower_bound(p)
    d = None if c is None else s.lower_bound(c+1)
    b = s.upper_bound(p)
    a = None if b is None else s.upper_bound(b-1)
    
    a = a if a is not None else 0
    d = d if d is not None else N+1

    if b is None:
        if c is not None:
            ans += i*p*(d-c)
    elif c is None:
        ans += i*(b-a)*(N-p+1)
    else:
        ans += i*((b-a)*(c-p)+(p-b)*(d-c))

    s.insert(p)

print(ans)

print('時間計測')

Submission status: Wrong Answer

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

def main():
	N = int(input())
	p = list(map(int,input().split()))
	nl = [0]*N
	for i,num in enumerate(p):
		nl[num-1] = i+1
	
	nl.reverse()
	print(nl)
	
	class BinaryIndexedTree:
		
		# 初期化
		def __init__(self, size, default):
			self.size = size
			self.default = default
			self.BIT = [default]*(self.size+1)
 
		# function(max, min, plus, minus, etc...)
		def BIT_segfunc(self, x, y):
			return x+y
 
		def BIT_query(self, idx):
			ret = self.default
			while idx > 0:
				ret = self.BIT_segfunc(ret, self.BIT[idx])
				idx -= idx&(-idx)
			return ret
 
		# update
		def BIT_update(self, idx, x):
			while idx <= self.size:
				self.BIT[idx] = self.BIT_segfunc(self.BIT[idx], x)
				idx += idx&(-idx)
			return
 
		def BIT_range(self, x, y):
			return self.BIT_query(y)-self.BIT_query(x)
 
		# BIT確認用
		def BIT_print(self):
			print(self.BIT)
			
		def BIT_search(self, x):
			i = 0
			s = 0
			step = 1<<(self.size.bit_length()-1)
			while step:
				if i+step <= self.size and s + self.BIT[i+step] < x:
					i += step
					s += self.BIT[i]
				step >>= 1
			return i+1
	
	BIT = BinaryIndexedTree(N, 0)
	ans = 0
	for i,num in enumerate(nl):
		l = BIT.BIT_query(num)
		BIT.BIT_update(num, 1)
		r = i-l
		a = BIT.BIT_search(l-1) if l >= 2 else 0
		b = BIT.BIT_search(l) if l >= 1 else 0
		d = BIT.BIT_search(l+2) if r >= 1 else N+1
		e = BIT.BIT_search(l+3) if r >= 2 else N+1
		ret = 0
		if b != 0:
			ret += (b-a)*(d-num)
		if d != 0:
			ret += (e-d)*(num-b)
		ans += ret*(N-i)
	print(ans)
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i

  #二分探索、x[未満or以下]のインデックス+1を返します
  def bs(self,x,side="l"):
    k = 1<<(self.bl-1)
    i = 0
    sm = 0
    flg = int(side!="l")
    while k:
      while i+k > self.size:
        k //= 2
      if sm+self.tree[i+k] < x+flg:
        sm += self.tree[i+k]
        i += k
      k //= 2
    return i+1

n = int(input())
a = list(map(int,input().split()))
da = {a[i]:i+1 for i in range(n)}
ans = 0
bit = Bit(n)
for i in range(n,0,-1):
  idx = da[i]
  x = bit.sum(idx)
  l2 = bit.bs(x-1,"l")
  l1 = bit.bs(x,"l")
  r1 = bit.bs(x+1,"l")
  r2 = bit.bs(x+2,"l")
  if i == n:
    bit.add(idx,1)
    continue
  if l1 == 1:
    l2 = 0
  if r1 == n+1:
    r2 = n+2
  if x == 0:
    ans += idx*(r2-r1)*i
  elif r1 == n+1:
    ans += (n-idx+1)*(l1-l2)*i
  else:
    if r1 < r2:
      ans += (r2-r1)*(idx-l1)*i
    if l2 < l1:
      ans += (l1-l2)*(r1-idx)*i
  bit.add(idx,1)
print(ans)

Submission status: Wrong Answer

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i

  #二分探索、x[未満or以下]のインデックス+1を返します
  def bs(self,x,side="l"):
    k = 1<<(self.bl-1)
    i = 0
    sm = 0
    flg = int(side!="l")
    while k:
      while i+k > self.size:
        k //= 2
      if sm+self.tree[i+k] < x+flg:
        sm += self.tree[i+k]
        i += k
      k //= 2
    return i+1

n = int(input())
a = list(map(int,input().split()))
da = {a[i]:i+1 for i in range(n)}
ans = 0
bit = Bit(n)
for i in range(n,0,-1):
  idx = da[i]
  x = bit.sum(idx)
  l2 = bit.bs(x-1,"l")
  l1 = bit.bs(x,"l")
  r1 = bit.bs(x+1,"l")
  r2 = bit.bs(x+2,"l")
  if l1 == 1:
    l2 = 0
  if r1 == n+1:
    r2 = n+2
  if x == 0:
    ans += idx*(r2-r1)*i
  elif r1 == n+1:
    ans += (n-idx+1)*(l1-l2)*i
  else:
    if r1 < r2:
      ans += (r2-r1)*(idx-l1)*i
    if l2 < l1:
      ans += (l1-l2)*(r1-idx)*i
  bit.add(idx,1)
  print(idx,ans)
  print(l2,l1,r1,r2)
print(ans)

Submission status: Wrong Answer

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i

  #二分探索、x[未満or以下]のインデックス+1を返します
  def bs(self,x,side="l"):
    k = 1<<(self.bl-1)
    i = 0
    sm = 0
    flg = int(side!="l")
    while k:
      while i+k > self.size:
        k //= 2
      if sm+self.tree[i+k] < x+flg:
        sm += self.tree[i+k]
        i += k
      k //= 2
    return i+1

n = int(input())
a = list(map(int,input().split()))
da = {a[i]:i+1 for i in range(n)}
ans = 0
bit = Bit(n)
for i in range(n,0,-1):
  idx = da[i]
  x = bit.sum(idx)
  l2 = bit.bs(x-1,"l")
  l1 = bit.bs(x,"l")
  r1 = bit.bs(x+1,"l")
  r2 = bit.bs(x+2,"l")
  if l1 == 1:
    l2 = 0
  elif r1 == n+1:
    r2 = n+2
  if x == 0:
    ans += idx*(r2-r1)*i
  elif r1 == n+1:
    ans += (n-idx+1)*(l1-l2)*i
  else:
    if r1 < r2:
      ans += (r2-r1)*(idx-l1)*i
    if l2 < l1:
      ans += (l1-l2)*(r1-idx)*i
  bit.add(idx,1)
print(ans)

Submission status: Wrong Answer

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

def get_de(p):
    d, e = [n for i in range(n)], [n for i in range(n)]
    stack1 = []
    stack2 = []
    for i in range(n):
        while stack2 and p[stack2[-1]] < p[i]:
            idx = stack2.pop()
            e[idx] = i

        while stack1 and p[stack1[-1]] < p[i]:
            idx = stack1.pop()
            d[idx] = i
            stack2.append(idx)
        stack1.append(i)

    dist1, dist2 = [], []
    for i in range(n):
        dist1.append(d[i] - i)
        dist2.append(e[i] - d[i])
    return dist1, dist2

dist1, dist2 = get_de(p)

dist3, dist4 = get_de(p[::-1])
dist3, dist4 = dist3[::-1], dist4[::-1]

ans = 0
for i in range(n):
    ans += (dist1[i] * dist4[i] + dist2[i] * dist3[i]) * p[i]
print(ans)

Submission status: Wrong Answer

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

def get_de(p):
    d, e = [n for i in range(n)], [n for i in range(n)]
    stack1 = []
    stack2 = []
    for i in range(n):
        while stack2 and p[stack2[-1]] < p[i]:
            idx = stack2.pop()
            e[idx] = i

        while stack1 and p[stack1[-1]] < p[i]:
            idx = stack1.pop()
            d[idx] = i
            stack2.append(idx)
        stack1.append(i)

    dist1, dist2 = [], []
    for i in range(n):
        dist1.append(d[i] - i)
        dist2.append(e[i] - d[i])
    return dist1, dist2

dist1, dist2 = get_de(p)

dist4, dist3 = get_de(p[::-1])
dist3, dist4 = dist3[::-1], dist4[::-1]

ans = 0
for i in range(n):
    ans += (dist1[i] * dist3[i] + dist2[i] * dist4[i]) * p[i]
print(ans)