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=int(input())
P=list(map(int,input().split()))
P.sort()
ans=0
for i in range(1,N):
  ans+=P[i-1]*i
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [None] + list(map(int, input().split()))

p_to_index = [None] * (N + 1)
for index, x in enumerate(P[1:], 1):
    p_to_index[x] = index


def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i & (-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i & (-i)
    return s

def BIT_search(x):
    i = 0
    s = 0
    step = 1 << (len(bin(N)[2:]) - 1)
    while step:
        if i + step <= N and s + tree[i + step] < x:
            i += step
            s += tree[i]
        step >>= 1
    return i + 1

tree = [0] * (N + 1)
ans = 0
for x in range(N, 0, -1):
    c = p_to_index[x]
    L = BIT_sum(c) -1
    R = N - x - L
    a = BIT_search(L - 1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L + 1) if R >= 1 else N + 1
    e = BIT_search(L + 2) if R >= 2 else N + 1
    BIT_add(c)
    tmp = 0
    if b != 0:
        tmp += (b - a) * (d - c)
    if d != 0:
        tmp += (e - d) * (c - b)
    ans += tmp * x

print (ans)

Submission status: Wrong Answer

Solution code:


INF = 10 * 6

class SegTree():
    def __init__(self, A):
        n_ = len(A)
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.tree = [INF for _ in range(2 * self.n - 1)]
        for k, a in enumerate(A):
            self.update(k, a)
    def update(self, k, a):
        k += self.n - 1
        self.tree[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])
    def query(self, l, r):
        l += self.n - 1
        r += self.n - 2
        res = INF
        while r-l>1:
            if l&1 == 0:
                res = min(res,self.tree[l])
            if r&1 == 1:
                res = min(res,self.tree[r])
                r -= 1
            l = l//2
            r = (r-1)//2
        if l == r:
            res = min(res,self.tree[l])
        else:
            res = min(min(res,self.tree[l]),self.tree[r])
        return res


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

pii = []

for i, pi in enumerate(p):
    pii.append([pi, i])

pii.sort(reverse=True)

st_r = SegTree([n] * (n+1))
st_l = SegTree([1] * (n+1))

ans = 0

for pi, i in pii:
    # print("###")
    # print(pi, i)
    # print(st_r.tree)
    if pi < n:
        l = -st_l.query(0, i)
        r = st_r.query(i+1, n)
        # print(l, r)
        if l != -1:
            l2 = l - 1
            if l > 0:
                l2 = -st_l.query(0, l)
            ans += (l - l2) * (r - i) * pi
        if r != n:
            r2 = r + 1
            if r < n - 1:
                r2 = st_r.query(r+1, n)
            ans += (i - l) * (r2 - r) * pi

    st_r.update(i, i)
    st_l.update(i, -i)

    
print(ans)

Submission status: Wrong Answer

Solution code:
class SparseTable:
    def __init__(self, a, func=max, one=-10**18):
        self.table = [a[:]]
        self.n = len(a)
        self.logn = self.n.bit_length()
        self.func = func
        self.one = one

        for i in map(lambda x: 1 << x, range(self.logn - 1)):
            self.table.append([])
            for j in range(self.n - i * 2 + 1):
                self.table[-1].append(self.func(self.table[-2][j],
                                                self.table[-2][j + i]))

    def get_section(self, i, j):
        length = j - i
        log = length.bit_length() - 1
        if length <= 0:
            return self.one
        return self.func(self.table[log][i], self.table[log][j - length])


def low(m, x):
    mi = 0
    ma = m - 1
    if ma < 0 or sp.get_section(0, m+1) <= x:
        return - 1
    while mi != ma:
        mm = (mi + ma) // 2 + 1
        if sp.get_section(mm, m+1) > x:
            mi = mm
        else:
            ma = mm - 1
    return mi


def high(m, x):
    mi = m
    ma = n - 1
    if m >= n or sp.get_section(m, n) <= x:
        return n
    while mi != ma:
        mm = (mi + ma) // 2
        if sp.get_section(m, mm+1) > x:
            ma = mm
        else:
            mi = mm + 1
    return mi


n = int(input())
p = [int(i) for i in input().split()]

sp = SparseTable(p)

ans = 0
for i in range(n):
    j = low(i, p[i])
    k = low(j, p[i])
    l = high(i, p[i])
    m = high(l+1, p[i])
    ans += p[i] * ((i-j) * (m-l) + (j-k) * (l-i))
print(ans)

Submission status: Wrong Answer

Solution code:
class SparseTable:
    def __init__(self, a, func=max, one=-10**18):
        self.table = [a[:]]
        self.n = len(a)
        self.logn = self.n.bit_length()
        self.func = func
        self.one = one

        for i in map(lambda x: 1 << x, range(self.logn - 1)):
            self.table.append([])
            for j in range(self.n - i * 2 + 1):
                self.table[-1].append(self.func(self.table[-2][j],
                                                self.table[-2][j + i]))

    def get_section(self, i, j):
        length = j - i
        log = length.bit_length() - 1
        if length <= 0:
            return self.one
        return self.func(self.table[log][i], self.table[log][j - length])


def low(m, x):
    mi = 0
    ma = m - 1
    if ma < 0 or sp.get_section(0, m) <= x:
        return - 1
    while mi != ma:
        mm = (mi + ma) // 2 + 1
        if sp.get_section(mm, m) > x:
            mi = mm
        else:
            ma = mm - 1
    return mi


def high(m, x):
    mi = m
    ma = n - 1
    if m >= n or sp.get_section(m, n) <= x:
        return n
    while mi != ma:
        mm = (mi + ma) // 2
        if sp.get_section(m, mm+1) > x:
            ma = mm
        else:
            mi = mm + 1
    return mi


n = int(input())
p = [int(i) for i in input().split()]

sp = SparseTable(p)

ans = 0
for i in range(n):
    j = low(i, p[i])
    k = low(j, p[i])
    l = high(i, p[i])
    m = high(l+1, p[i])
    ans += p[i] * ((i-j) * (m-l) + (j-k) * (l-i))
print(ans)

Submission status: Wrong Answer

Solution code:
class SparseTable:
    def __init__(self, a, func=max, one=-10**18):
        self.table = [a[:]]
        self.n = len(a)
        self.logn = self.n.bit_length()
        self.func = func
        self.one = one

        for i in map(lambda x: 1 << x, range(self.logn - 1)):
            self.table.append([])
            for j in range(self.n - i * 2 + 1):
                self.table[-1].append(self.func(self.table[-2][j],
                                                self.table[-2][j + i]))

    def get_section(self, i, j):
        length = j - i
        log = length.bit_length() - 1
        if length <= 0:
            return self.one
        return self.func(self.table[log][i], self.table[log][j - length])


def low(m, x):
    mi = 0
    ma = m - 1
    if ma < 0 or sp.get_section(0, m) <= x:
        return - 1
    while mi != ma:
        mm = (mi + ma) // 2 + 1
        if sp.get_section(mm, m) > x:
            mi = mm
        else:
            ma = mm - 1
    return mi


def high(m, x):
    mi = m
    ma = n - 1
    if m >= n or sp.get_section(m, n) <= x:
        return n
    while mi != ma:
        mm = (mi + ma) // 2
        if sp.get_section(m, mm+1) > x:
            ma = mm
        else:
            mi = mm + 1
    return mi


n = int(input())
p = [int(i) for i in input().split()]

sp = SparseTable(p)

ans = 0
for i in range(n):
    j = low(i, p[i])
    k = low(j, p[i])
    l = high(i+1, p[i])
    m = high(l+1, p[i])
    ans += p[i] * ((i-j) * (m-l) + (j-k) * (l-i))
print(ans)

Submission status: Wrong Answer

Solution code:
class SparseTable:
    def __init__(self, a, func=max, one=-10**18):
        self.table = [a[:]]
        self.n = len(a)
        self.logn = self.n.bit_length()
        self.func = func
        self.one = one

        for i in map(lambda x: 1 << x, range(self.logn - 1)):
            self.table.append([])
            for j in range(self.n - i * 2 + 1):
                self.table[-1].append(self.func(self.table[-2][j],
                                                self.table[-2][j + i]))

    def get_section(self, i, j):
        length = j - i
        log = length.bit_length() - 1
        if length <= 0:
            return self.one
        return self.func(self.table[log][i], self.table[log][j - length])


def low(m, x):
    mi = 0
    ma = m - 1
    if ma < 0 or sp.get_section(0, ma) <= x:
        return - 1
    while mi != ma:
        mm = (mi + ma) // 2 + 1
        if sp.get_section(mm, m) > x:
            mi = mm
        else:
            ma = mm - 1
    return mi


def high(m, x):
    mi = m + 1
    ma = n - 1
    if m >= n or sp.get_section(m+1, n) <= x:
        return n
    while mi != ma:
        mm = (mi + ma) // 2
        if sp.get_section(m, mm+1) > x:
            ma = mm
        else:
            mi = mm + 1
    return mi


n = int(input())
p = [int(i) for i in input().split()]

sp = SparseTable(p)

ans = 0
for i in range(n):
    j = low(i, p[i])
    k = low(j, p[i])
    l = high(i, p[i])
    m = high(l, p[i])
    ans += p[i] * ((i-j) * (m-l) + (j-k) * (l-i))
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

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)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        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


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

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



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

order = [-1 for i in range(n+1)]
for i in range(n):
    order[data[i]]=i

sqn = int(math.sqrt(n)+1)



myLeft = [-1 for i in range(n)]
myRight = [n for i in range(n)]

list1 = [0 for i in range(sqn*sqn)]
list2 = [0 for i in range(sqn)]

for i in range(n,0,-1):
    ## add data
    list1[order[i]] = 1
    list2[order[i]//sqn] = 1
    
    ## find L
    #stage-1
    left = -1
    pos2 = order[i]//sqn
    pos1 = order[i] %sqn - 1
    
    while(pos1 >= 0):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            left = now
            break
        else:
            pos1 -= 1
            
    if(left >= 0):
        myLeft[order[i]] = left
        continue

    #stage-2
    pos2 -= 1
    while(pos2 >= 0):
        if(list2[pos2] == 1):
            break
        else:
            pos2-=1
    if(pos2<0):
        continue
    
    #stage-3
    pos1 = sqn-1
    while(pos1 >= 0):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            left = now
            break
        else:
            pos1 -= 1

    if(left >= 0):
        myLeft[order[i]] = left
        continue

#print(list1,list2,myLeft)


list1 = [0 for i in range(sqn*sqn)]
list2 = [0 for i in range(sqn)]

for i in range(n,0,-1):
    ## add data
    list1[order[i]] = 1
    list2[order[i]//sqn] = 1
    
    ## find L
    #stage-1
    right = -1
    pos2 = order[i]//sqn
    pos1 = order[i] %sqn + 1
    
    while(pos1 < sqn):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            right = now
            break
        else:
            pos1 += 1
            
    if(right >= 0):
        myRight[order[i]] = right
        continue

    #stage-2
    pos2 += 1
    while(pos2 < sqn):
        if(list2[pos2] == 1):
            break
        else:
            pos2+=1
    if(pos2>=sqn):
        continue
    
    #stage-3
    pos1 = 0
    while(pos1 < sqn):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            right = now
            break
        else:
            pos1 += 1

    if(right >= 0):
        myRight[order[i]] = right
        continue

#print(list1,list2,myRight)

ans = 0

for i in range(n):
    if(myLeft[i]!=-1):
        numLeft = myLeft[i] - myLeft[myLeft[i]]
        numRight = myRight[i] - i
        #print(i,"L",numLeft,numRight)
        ans += data[i] * numLeft * numRight
    if(myRight[i]!=n):
        numLeft = i - myLeft[i]
        numRight = myRight[myRight[i]] - myRight[i]
        #print(i,"R",numLeft,numRight)
        ans += data[i] * numLeft * numRight

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

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)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        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


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

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



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

order = [-1 for i in range(n+1)]
for i in range(n):
    order[data[i]]=i

sqn = int(math.sqrt(n)+1)



myLeft = [-1 for i in range(n)]
myRight = [n for i in range(n)]

list1 = [0 for i in range(sqn*sqn)]
list2 = [0 for i in range(sqn)]

for i in range(n,0,-1):
    ## add data
    list1[order[i]] = 1
    list2[order[i]//sqn] = 1
    
    ## find L
    #stage-1
    left = -1
    pos2 = order[i]//sqn
    pos1 = order[i] %sqn - 1
    
    while(pos1 >= 0):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            left = now
            break
        else:
            pos1 -= 1
            
    if(left >= 0):
        myLeft[order[i]] = left
        continue

    #stage-2
    pos2 -= 1
    while(pos2 >= 0):
        if(list2[pos2] == 1):
            break
        else:
            pos2-=1
    if(pos2<0):
        continue
    
    #stage-3
    pos1 = sqn-1
    while(pos1 >= 0):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            left = now
            break
        else:
            pos1 -= 1

    if(left >= 0):
        myLeft[order[i]] = left
        continue

print(list1,list2,myLeft)


list1 = [0 for i in range(sqn*sqn)]
list2 = [0 for i in range(sqn)]

for i in range(n,0,-1):
    ## add data
    list1[order[i]] = 1
    list2[order[i]//sqn] = 1
    
    ## find L
    #stage-1
    right = -1
    pos2 = order[i]//sqn
    pos1 = order[i] %sqn + 1
    
    while(pos1 < sqn):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            right = now
            break
        else:
            pos1 += 1
            
    if(right >= 0):
        myRight[order[i]] = right
        continue

    #stage-2
    pos2 += 1
    while(pos2 < sqn):
        if(list2[pos2] == 1):
            break
        else:
            pos2+=1
    if(pos2>=sqn):
        continue
    
    #stage-3
    pos1 = 0
    while(pos1 < sqn):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            right = now
            break
        else:
            pos1 += 1

    if(right >= 0):
        myRight[order[i]] = right
        continue

print(list1,list2,myRight)

ans = 0

for i in range(n):
    if(myLeft[i]!=-1):
        numLeft = myLeft[i] - myLeft[myLeft[i]]
        numRight = myRight[i] - i
        #print(i,"L",numLeft,numRight)
        ans += data[i] * numLeft * numRight
    if(myRight[i]!=n):
        numLeft = i - myLeft[i]
        numRight = myRight[myRight[i]] - myRight[i]
        #print(i,"R",numLeft,numRight)
        ans += data[i] * numLeft * numRight

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

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)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        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


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

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



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

order = [-1 for i in range(n+1)]
for i in range(n):
    order[data[i]]=i

sqn = int(math.sqrt(n)+1)



myLeft = [-1 for i in range(n)]
myRight = [n for i in range(n)]

list1 = [0 for i in range(sqn*sqn)]
list2 = [0 for i in range(sqn)]

for i in range(n,0,-1):
    ## add data
    list1[order[i]] = 1
    list2[order[i]//sqn] = 1
    
    ## find L
    #stage-1
    left = -1
    pos2 = order[i]//sqn
    pos1 = order[i] %sqn - 1
    
    while(pos1 >= 0):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            left = now
            break
        else:
            pos1 -= 1
            
    if(left >= 0):
        myLeft[order[i]] = left
        continue

    #stage-2
    pos2 -= 1
    while(pos2 >= 0):
        if(list2[pos2] == 1):
            break
        else:
            pos2-=1
    if(pos2<0):
        continue
    
    #stage-3
    pos1 = sqn-1
    while(pos1 >= 0):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            left = now
            break
        else:
            pos1 -= 1

    if(left >= 0):
        myLeft[order[i]] = left
        continue

print(list1,list2,myLeft)


list1 = [0 for i in range(sqn*sqn)]
list2 = [0 for i in range(sqn)]

for i in range(n,0,-1):
    ## add data
    list1[order[i]] = 1
    list2[order[i]//sqn] = 1
    
    ## find L
    #stage-1
    right = -1
    pos2 = order[i]//sqn
    pos1 = order[i] %sqn + 1
    
    while(pos1 < sqn):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            right = now
            break
        else:
            pos1 += 1
            
    if(right >= 0):
        myRight[order[i]] = right
        continue

    #stage-2
    pos2 += 1
    while(pos2 < sqn):
        if(list2[pos2] == 1):
            break
        else:
            pos2+=1
    if(pos2>=sqn):
        continue
    
    #stage-3
    pos1 = 0
    while(pos1 < sqn):
        now = pos2*sqn + pos1
        if(list1[now] == 1):
            right = now
            break
        else:
            pos1 += 1

    if(right >= 0):
        myRight[order[i]] = right
        continue

print(list1,list2,myRight)

ans = 0

for i in range(n):
    if(myLeft[i]!=-1):
        numLeft = myLeft[i] - myLeft[myLeft[i]]
        numRight = myRight[i] - i
        print(i,"L",numLeft,numRight)
        ans += data[i] * numLeft * numRight
    if(myRight[i]!=n):
        numLeft = i - myLeft[i]
        numRight = myRight[myRight[i]] - myRight[i]
        print(i,"R",numLeft,numRight)
        ans += data[i] * numLeft * numRight

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N=int(input())
plist=list(map(int,input().split()))

pi_list=[]
for i in range(N):
  pi_list.append((plist[i],i))
pi_list.sort()
#print(pi_list)

answer=0
hq_s=[1,1]
heapq.heapify(hq_s)
hq_t=[N,N]
heapq.heapify(hq_t)
for i in reversed(range(N)):
  p1,i1=pi_list[i]
  if i<N-1:
    p2,i2=pi_list[i+1]
    if i1>i2:
      heapq.heappush(hq_s,-i2)
    else:
      heapq.heappush(hq_t,i2)
    
  x=-heapq.heappop(hq_s)
  w=-heapq.heappop(hq_s)
  heapq.heappush(hq_s,-w)
  heapq.heappush(hq_s,-x)
  y=heapq.heappop(hq_t)
  z=heapq.heappop(hq_t)
  heapq.heappush(hq_t,z)
  heapq.heappush(hq_t,y)
  #print(w,x,i1,y,z)
  
  ci=(x-w)*(y-i1)+(i1-x)*(z-y)
  answer+=ci*p1
  
print(answer)

Submission status: Wrong Answer

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    class Bit():
        def __init__(self, n):
            n = 1<<(n.bit_length())
            self.size = n
            self.tree = [0] * (n + 1)
            return

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

        def add(self, i, x=1):
            # i==0 はだめ => 全部+1するとか
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def search(self, x):
            # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
            # maspyさんの参考
            i = 0
            s = 0
            step = 1 << (self.size - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < x:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return i + 1

        def debug(self, k):
            return [self.sum(i) for i in range(k)]

    N = I()
    P = LI()
    Order = [[i+1] for i in range(N)]
    for i,p in enumerate(P):
        Order[i].append(p)
    Order.sort(key=lambda x:x[1],reverse=True)
    print(Order)
    ans = 0
    bit = Bit(N+2)

    for i,p in Order:
        L = bit.sum(i)
        R = bit.sum(N)-L
        bit.add(i)
        l0, l1, r0, r1 = 0, 0, N+1, N+1
        if L>=2:
            l0 = bit.search(L-1)
        if L>=1:
            l1 = bit.search(L)
        if R>=1:
            r0 = bit.search(L+2)
        if R>=2:
            r1 = bit.search(L+3)
        #print(L,R)
        #print(l0,l1,r0,r1)
        #print(bit.debug(N+2))
        cnt = 0
        if l1>0:
            cnt += (l1-l0)*(r0-i)
        if r0>0:
            cnt += (i-l1)*(r1-r0)
        ans += cnt * p
        #print(ans)
    print(ans)
    return

def examF():
    def bfs(n, e, S):
        W = [0]*(2**n)
        cur = 1
        que = deque()
        que.append(e)
        while cur<2**n:
            now = que.popleft()
            depth = W[now]
            if S[now]<=S[cur]:
                return "No"
            for ne in range(n-depth):
                cur +=1
                W[now+1+ne] = depth+1
                que.append(now+1+ne)
        return "Yes"
    N = I()
    S = LI(); S.sort(reverse=True)
    ans = bfs(N,0,S)
    print(ans)
    return


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Wrong Answer

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

index=[0]
for i in range(1,n+1):
  index.append(p.index(i)+1)

s=[0,0,index[n],n+1,n+1]
a=[]

import bisect
for i in reversed(range(1,n)):
  bisect.insort(s,index[i])
  t=s.index(index[i])
  
  w=s[t-2]
  x=s[t-1]
  y=s[t+1]
  z=s[t+2]
  c=(x-w)*(y-index[i])+(index[i]-x)*(z-y)
  a.append(i*c)

print(sum(a))
print(s)

Submission status: Wrong Answer

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

index=[0]
for i in range(1,n+1):
  index.append(p.index(i)+1)

s=[0,0,index[n],n+1,n+1]
a=[]

import bisect
for i in reversed(range(1,n)):
  bisect.insort_left(s,index[i])
  t=s.index(index[i])
  
  w=s[t-2]
  x=s[t-1]
  y=s[t+1]
  z=s[t+2]
  c=(x-w)*(y-index[i])+(index[i]-x)*(z-y)
  a.append(i*c)

print(sum(a))
print(s)

Submission status: Wrong Answer

Solution code:
n=int(input())
p=list(map(int,input().split()))
s=[0,0]
t=[n+1,n+1]
a=[]
for i in reversed(range(1,n)):
  if p.index(i)<p.index(i+1):
    t.append(p.index(i+1)+1)
  elif p.index(i)>p.index(i+1):
    s.append(p.index(i+1)+1)
  w=sorted(s)[-1]
  x=sorted(s)[-2]
  y=sorted(t)[0]
  z=sorted(t)[1]
  c=(w-x)*(y-p.index(i)-1)+(p.index(i)+1-w)*(z-y)
  a.append(i*c)
print(sum(a))