Problem:


Score : 400 points

Problem Statement

One day, Snuke was given a permutation of length N, a_1, a_2, ..., a_N, from his friend.

Find the following:

Constraints

1 ≦ N ≦ 200,000

(a_1, a_2, ..., a_N) is a permutation of (1, 2, ..., N).

Input

The input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the answer.

Note that the answer may not fit into a 32-bit integer.

Sample Input 1

3
2 1 3

Sample Output 1

9

Sample Input 2

4
1 3 2 4

Sample Output 2

19

Sample Input 3

8
5 4 8 1 2 6 7 3

Sample Output 3

85



Sample input:
3
2 1 3


Sample output:
9

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = 10

N = read()
a = [x-1 for x in reads()]
b = [0] * N
for i in range(N):
  b[a[i]] = i

class BITD:
  def __init__(self, n):
    self.size = n
    self._body = [-1] * (n+1)
  def __repr__(self):
    return ("BIT([" + ", ".join(str(self.at(i)) for i in range(self.size)) + "])")
  def ins(self, i):
    v = i
    i += 1
    while(i <= self.size):
      self._body[i] = max(self._body[i], v)
      i += i & -i
  def at(self, i): # max{x | x in self and x <= i}
    i += 1
    s = -1
    while(i > 0):
      s = max(s, self._body[i])
      i -= i & -i
    return s

class BITU:
  def __init__(self, n):
    self.size = n
    self._body = [N] * (n+1)
  def __repr__(self):
    return ("BIT([" + ", ".join(str(self.at(i)) for i in range(self.size)) + "])")
  def ins(self, i):
    v = i
    i = self.size-1 - i
    i += 1
    while(i <= self.size):
      self._body[i] = min(self._body[i], v)
      i += i & -i
  def at(self, i): # max{x | x in self and x <= i}
    i = self.size-1 - i
    i += 1
    s = N
    while(i > 0):
      s = min(s, self._body[i])
      i -= i & -i
    return s

setrecursionlimit(1000000)

bit_u = BITU(N)
bit_d = BITD(N)

res = 0
for i in range(N):
  u = bit_u.at(b[i])
  d = bit_d.at(b[i])
  # print((u - b[i]), (b[i] - d), (i+1))
  res += (u - b[i]) * (b[i] - d) * (i+1)

  bit_u.ins(b[i])
  bit_d.ins(b[i])

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys 

N = int(sys.stdin.readline())
P = [int(x) for x in sys.stdin.readline().split()]

SUM = sum([sum([min(P[l:r+1]) for r in range(l, N)]) for l in range(N)])

print(SUM)

Submission status: Time Limit Exceeded

Solution code:
import sys 

N = int(sys.stdin.readline())
P = [int(x) for x in sys.stdin.readline().split()]

SUM = 0 

for l in range(N):
    SUM += sum([min(P[l:r+1]) for r in range(l, N)])

print(SUM)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr=list(map(int,input().split()))
z = sorted(list(zip(arr,list(range(1,n+1)))))
brr = [0]*(n+2)
brr[0]=1
brr[-1]=1
ans=0
for p in z:
    sm=0
    for i in range(p[1],-1,-1):
        if brr[i]==1:
            sm=i
            break
    lg=n+1
    for i in range(p[1],n+2):
        if brr[i]==1:
            lg=i
            break
    ans+=(lg-p[1])*(p[1]-sm)*p[0]
    brr[p[1]]=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding=UTF-8

N=int(input())

mojir=input()
hyo=mojir.split(' ')
a=[int(mono) for mono in hyo]

ans=0

retu=a+[0]
for idx in range(0,N,1):
    ans=ans+sum(retu)
    for idy in range(0,N-idx,1):
        retu[idy]=min(retu[idy],retu[idy+1])
    retu[N-idx]=0
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
ans = 0
for i in range(n):
        min_num = min(a[i:])
        min_index = a.index(min_num)
        for j in range(i+1, min_index+1):
                ans += min(a[i:j])
        ans += min_num * (n - min_index)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys 

N = int(sys.stdin.readline())
P = [int(x) for x in sys.stdin.readline().split()]

SUM = 0 

for l in range(N):
    for r in range(l, N): 
        SUM += min(P[l:r+1])

print(SUM)

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
n = map(int, raw_input().split())

total = 0
for i in xrange(N):
    for j in xrange(i,N):
        total+=min(n[i:j+1])

print total

Submission status: Time Limit Exceeded

Solution code:
#coding=UTF-8

N=int(input())

mojir=input()
hyo=mojir.split(' ')
a=[int(mono) for mono in hyo]

ans=0

retu=[N+1]*N
for idx in range(0,N,1):
    tmp=[]
    for idy in range(0,N-idx,1):
        tmp.append(min(retu[idy],a[idx+idy]))

    retu=tmp
    ans=ans+sum(retu)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
array = list(map(int,list(input().split())))
ans = 0
minimum = 0

for l in range(0,N):
    r = N
    while r > l:
        minimum = min(array[l:r])
        ans += minimum * (r - array.index(minimum))
        r = array.index(minimum)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
A = list(map(int, input().split()))
L = []
args = [0 for _ in range(N + 1)]
for i, a in enumerate(A):
    args[a] = i + 1
ans = 0
for n in range(1, N + 1):
    if n == 1:
        ans += args[n] * (N - args[n] + 1)
        L.append(args[n])
    else:
        ins = bisect.bisect_left(L, args[n])
        if ins == 0:
            l = args[n]
        else:
            l = args[n] - L[ins-1]
        if ins == len(L):
            r = N - args[n] + 1
        else:
            r = L[ins] - args[n]
        # print(n, ins, l, r)
        ans += l * r * n
        bisect.insort_left(L, args[n])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
l = map(int, raw_input().split())
r = [min([l[k] for k in xrange(i, j+1)]) for i in xrange(n) for j in xrange(i,n)]
print sum(r)

Submission status: Time Limit Exceeded

Solution code:
def s():
    return raw_input()
def li():
    return map(int,raw_input().split())
N = int(s())
a = li()
s = 0
dp = [[0 for i in range(N+2)] for j in range(N+1) ]

for i in range(1,N+1):
    dp[i][i] = a[i-1]
    for k in range(i,N+1):
        dp[i][k+1] = min(dp[i][k],a[k-1])
    s += sum(dp[i])

print s-sum(a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
aa = [int(s) - 1 for s in input().split()]
index = [None] * N
for i,a in enumerate(aa):
    index[a] = i

intervals = {(0,N-1)}
sum = 0
for k,ind in enumerate(index,1):
    n1,n2 = next(itv for itv in intervals if itv[0] <= ind <= itv[1])
    intervals.remove((n1,n2))
    sum += k * (ind-n1+1) * (n2-ind+1)
    if n1 < n2:
        if ind == n1:
            intervals.add((n1+1,n2))
        elif ind == n2:
            intervals.add((n1,n2-1))
        else:
            intervals.add((n1,ind-1))
            intervals.add((ind+1,n2))
print(sum)

Submission status: Time Limit Exceeded

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

sum = 0

old_m_list = []

for l in reversed(range(0,len(a))):
    sum += a[l]
    m_list = []
    m_list.append(a[l])

    for r in old_m_list:
        mi = min(a[l],r)
        sum += mi
        m_list.append(mi)

    old_m_list = m_list

print sum

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def s():
    return raw_input()
def li():
    return map(int,raw_input().split())

N = int(s())
a = li()
s = 0
dp = np.array([[0 for i in range(N+2)] for j in range(N+1) ])

for i in range(1,N+1):
    dp[i][i] = a[i-1]
    for k in range(i,N+1):
        dp[i][k+1] = min(dp[i][k],a[k-1])
    s += sum(dp[i])

print s-sum(np.diag(dp))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
ans = 0
for i in range(n):
    for j in range(i, n):
        ans += min(a[i:j+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
array = list(map(int,list(input().split())))
ans = 0

for l in range(0,N):
    for r in range(l+1,N+1):
        ans += min(array[l:r])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N=int(raw_input())
A=[int(x) for x in raw_input().split()]
K=[-1,N]
B=range(N+1)
ans=0
for i in range(N):
    a=A[i]
    B[a]=i
for i in range(1,N+1):
    loc=B[i]
    l=bisect.bisect(K,loc)-1
    r=bisect.bisect(K,loc)
    lloc=K[l]
    rloc=K[r]
    ans+=(loc-lloc)*(rloc-loc)*i
    bisect.insort(K,loc)
print ans

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
c = 0
a = list(map(int,input().split()))
for l in range(N):
	for r in range(l,N):
		c += min(a[l:r+1])
print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
array = list(map(int,list(input().split())))
ans = 0

for l in range(0,N):
    for r in range(l+1,N+1):
        another_array = array[l:r]
        if min(another_array) == 1:
            ans += 1
        else:
            ans += min(another_array)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
result = 0
for i in range(N):
    for j in range(i, N):
        result += min(a[i:j + 1])
print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
permutation_str = raw_input()
permutation_list = map(int, permutation_str.split(' '))
permutation_sum = permutation_list[0]
prior_list = [permutation_list[0]]

for i in range(1, n):
    current_num = permutation_list[i]
    for j in range(len(prior_list)):
        if prior_list[j] > current_num:
            prior_list[j] = current_num
    prior_list.append(current_num)
    permutation_sum += sum(prior_list)

print permutation_sum

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
array = list(map(int,list(input().split())))
ans = 0

for l in range(0,N):
    for r in range(l+1,N+1):
        another_array = array[l:r]
        ans += min(another_array)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [int(i) for i in input().split()]
print(sum([min(a[l:r + 1]) for l in range(N) for r in range(l, N)]))

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
a = map(int,raw_input().split(' '))

ans = 0
for l in range(len(a)):
    for r in range(l,len(a)):
        array = a[l:r+1]
        #print array
        ans += min(array)

print ans

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
l = map(int, raw_input().split())
o = 0
for i in xrange(n):
    for j in xrange(i,n):
        r = []
        for k in xrange(i, j+1):
            r.append(l[k])
        o += min(r)
print o

Submission status: Time Limit Exceeded

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

sum = 0

for l in range(0,len(a)):
    sum += a[l]
    mi = a[l]
    for r in range(l,len(a)):
        if(r != l):
            mi = min(mi,a[r])
            sum += mi

print sum

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(sys.stdin.readline())
A = map(int,sys.stdin.readline().split())

res = 0
i = 0
while i < len(A):
        a = A[i]
        left = 0
        right = 0
        for b in reversed(A[:i]):
                if b > a:
                        left += 1
                else:
                        break
        for b in A[i+1:]:
                if b > a:
                        right += 1
                else:
                        break
        res += a * (left + 1) * (right + 1)
        i += 1                                                                                                                                                                                                                        

print res

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    mi = []
    def g(a, j):
        l = len(a)
        if l == 0:
            return 0
        if l == 1:
            return a[0]
        if a[0] == j:
            return l * j + g(a[1:], j+1)
        if a[-1] == j:
            return l * j + g(a[:l-1], j+1)
        m = min(a)
        i = a.index(m)
        return (i+1) * (l-i) * m + g(a[i+1:], m+1) + g(a[:i], m+1)
    return g(a, 1)

print(f())

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
a = [int(x) for x in raw_input().split(' ')]

MINlr = [[0 for x in range(N)] for y in range(N)]

def getMin(l, r):
    if (l == r):
        return a[l]
    else:
        return min(MINlr[l][r-1],a[r])
total = 0
for l in range(N):
    for r in range(l,N):
        if (l == r):
            MINlr[l][r] = a[r]
        else:
            MINlr[l][r] = min(MINlr[l][r-1],a[r])
        total += MINlr[l][r]
print total

Submission status: Time Limit Exceeded

Solution code:
def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def main():
    n = read()
    a = reads()
    ans = 0
    for i in range(0, n+1):
        for j in range(i, n):
            ans += min(a[i:j+1])
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys 
N = int(sys.stdin.readline())
A = map(int,sys.stdin.readline().split())

dpm = [[None for x in xrange(N)] for y in xrange(N)]
res = 0 
for i in xrange(N):
        for j in xrange(i, N): 
                if i == j:
                        res += A[i]
                        dpm[i][i] = A[i]
                else:
                        dpm[i][j] = min(dpm[i][j-1], A[j])
                        res += dpm[i][j]                                                                                                                                                                                              

print res

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    def g(a):
        l = len(a)
        if l == 0:
            return 0
        if l == 1:
            return a[0]
        m = min(a)
        i = a.index(m)
        return (i+1) * (l-i) * m + g(a[i+1:]) + g(a[:i])
    return g(a)

print(f())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
ans = 0

for i in range(1, n + 1):
    ans += sum(a)
    a = [min(i, j) for (i, j) in zip(a, a[1:])]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
A = [a-1 for a in A]

P = [-1]*n
for i, a in enumerate(A):
    P[a] = i

R = [n]*n
q = []
import heapq
heapq.heapify(q)
for i in range(n):
    while q:
        if -q[0] > A[i]:
            v = -heapq.heappop(q)
            R[v] = i
        else:
            break
    heapq.heappush(q, -A[i])

L = [-1]*n
q = []
heapq.heapify(q)
for i in reversed(range(n)):
    while q:
        if -q[0] > A[i]:
            v = -heapq.heappop(q)
            L[v] = i
        else:
            break
    heapq.heappush(q, -A[i])
#print(P)
#print(R)
#print(L)
ans = 0
for i in range(n):
    ans += (P[i]-L[i])*(R[i]-P[i])*(i+1)
print(ans)

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# cython: boundscheck=False, wraparound=False
from libcpp.set cimport set
from libcpp.vector cimport vector
from libc.stdio cimport getchar, printf
from cython.operator cimport dereference as deref
from cython.operator cimport preincrement as preinc, predecrement as predec
from cython.operator cimport postincrement as postinc, postdecrement as postdec
cdef int cin() nogil:
    cdef int b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: break
        c = c * 10 + b
    return c
cdef int n = cin(), i
cdef long c
cdef vector[long] a = vector[long](n)
for i in range(n): a[cin() - 1] = i
cdef set[long] s = set[long]([-1, n])
cdef set[long].iterator it
for i in range(n):
    it = s.lower_bound(a[i])
    c += (deref(postdec(it)) - a[i]) * (a[i] - deref(it)) * (i + 1)
    s.insert(a[i])
printf('%ld\n', c)
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# cython: wraparound=False
from libcpp.set cimport set
from libcpp.vector cimport vector
from libc.stdio cimport getchar, printf
from cython.operator cimport dereference as deref
from cython.operator cimport preincrement as preinc, predecrement as predec
from cython.operator cimport postincrement as postinc, postdecrement as postdec
cdef int cin() nogil:
    cdef int b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: break
        c = c * 10 + b
    return c
cdef int n = cin(), i
cdef long c
cdef vector[long] a = vector[long](n)
for i in range(n): a[cin() - 1] = i
cdef set[long] s = set[long]([-1, n])
cdef set[long].iterator it
for i in range(n):
    it = s.lower_bound(a[i])
    c += (deref(postdec(it)) - a[i]) * (a[i] - deref(it)) * (i + 1)
    s.insert(a[i])
printf('%ld\n', c)
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
from libcpp.set cimport set
from libcpp.vector cimport vector
from libc.stdio cimport getchar, printf
from cython.operator cimport dereference as deref
from cython.operator cimport preincrement as preinc, predecrement as predec
from cython.operator cimport postincrement as postinc, postdecrement as postdec
cdef int cin() nogil:
    cdef int b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: break
        c = c * 10 + b
    return c
cdef int n = cin(), i
cdef long c
cdef vector[long] a = vector[long](n)
for i in range(n): a[cin() - 1] = i
cdef set[long] s = set[long]([-1, n])
cdef set[long].iterator it
for i in range(n):
    it = s.lower_bound(a[i])
    c += (deref(postdec(it)) - a[i]) * (a[i] - deref(it)) * (i + 1)
    s.insert(a[i])
printf('%ld\n', c)
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${rg?P`QD5d7~`ER<5McXC316zM&QJxYwLw=|bXvi9iPcVn!*mIj3E%<Q-yxr3ep&rBvXV3ZwaHR4g1Wj1(s0YjahrYazVrpx3!gWP{{AE?>+jZWc@q6*xT+vpKlpOxRi<jL}obo!Ie&Q@+huWr41^f<_8HG&E$jG5S@_IN?d3D%kJaR4!tRGSxI-AJa%K+eW=JJ4{1!-8JVWDx2kiKi24txfXx@btV<Gzj|whXy*2>V3nbn}$cI4^Tq4z#e(_7H;aXQ50+10VUKpJANzDu-XWnK#BAg$Ze4gG7S<V@Uj{dqyg2Y9`{h6Bx7}zt*kadz%9z#eZ2#FD*mV{;&s-<|NLZWhB!J^#$D0Bb#AtOu38eS)O>k_eA!4&9IIJ48OI`$IB~L^$QKJkGN?M`hl*@K&#Ps64f(^p>0j-GY^un<0PhaYas")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
from libcpp.set cimport set
from libcpp.vector cimport vector
from cython.operator cimport dereference as deref, predecrement as dec
cdef int n = int(input()), i
cdef long c
cdef vector[long] a = [*map(int, input().split())]
cdef vector[long] l = [0] * n
for i in range(n): l[a[i] - 1] = i
cdef set[long] s = set[long]([-1, n])
cdef set[long].iterator it
for i in range(n):
    it = s.lower_bound(l[i])
    c += (deref(it) - l[i]) * (l[i] - deref(dec(it))) * (i + 1)
    s.insert(l[i])
print(c)
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
from libcpp.set cimport set
from libcpp.vector cimport vector
from libcpp.iterator cimport iterator
from cython.operator cimport dereference as deref, predecrement as dec
cdef int n = int(input()), i
cdef long c
cdef iterator it, jt
cdef vector[long] a = [*map(int, input().split())]
cdef vector[long] l = [0] * n
for i in range(n): l[a[i] - 1] = i
cdef set[long] s = set[long]([-1, n])
for i in range(n):
    c += (deref(s.lower_bound(l[i])) - l[i]) * (l[i] - deref(dec(s.lower_bound(l[i])))) * (i + 1)
    s.insert(l[i])
print(c)
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
class segTreeMin:
  # 区間最小値を求めるセグメント木
  inf = 10**10
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.inf = num
    s.T = [s.inf] * (2 * s.N)
  def do(s, l, r):
    #最小値
    return min(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i + 1, 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 get(s, x):
    return s.T[x + s.N - 1]
  def getArea(s, l, r):
    L = l + s.N
    R = r + s.N
    p = s.inf
    while L < R:
      if R & 1:
        R -= 1
        p = s.do(p, s.T[R - 1])
      if L & 1:
        p = s.do(p, s.T[L - 1])
        L += 1
      L >>= 1
      R >>= 1
    return p

class segTreeMax:
  # 区間最大値を求めるセグメント木
  inf = -1
  def __init__(s, num):
    s.N = 1
    while s.N < num:
      s.N *= 2
    s.T = [s.inf] * (2 * s.N)
  def do(s, l, r):
    #最大値
    return max(l, r)
  def set(s, L):
    for i in range(len(L)):
      s.update(i + 1, 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 get(s, x):
    return s.T[x + s.N - 1]
  def getArea(s, l, r):
    L = l + s.N
    R = r + s.N
    p = s.inf
    while L < R:
      if R & 1:
        R -= 1
        p = s.do(p, s.T[R - 1])
      if L & 1:
        p = s.do(p, s.T[L - 1])
        L += 1
      L >>= 1
      R >>= 1
    return p

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

segMax = segTreeMax(N)
segMin = segTreeMin(N)

D = [[0] * 2 for _ in range(N)]
L = [0] * N

for i in range(N):
  t = a[i] - 1
  L[t] = i
  
ans = 0
for i in range(N):
  l = segMax.getArea(0, L[i] + 1)
  r = segMin.getArea(L[i], N)
  ans += (i + 1) * (L[i] - l) * (r - L[i])
  segMax.update(L[i], L[i])
  segMin.update(L[i], L[i])

print(ans)

Submission status: Accepted

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

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

import heapq
q = []
heapq.heapify(q)
R = [n-1]*n
for i, a in enumerate(A):
    while q and q[0]*(-1) > a:
        v = heapq.heappop(q)*(-1)
        R[v-1] = i-1
    heapq.heappush(q, a*(-1))

q = []
L = [0]*n
for j in range(n):
    i = n-1-j
    a = A[i]
    while q and q[0]*(-1) > a:
        v = heapq.heappop(q)*(-1)
        L[v-1] = i+1
    heapq.heappush(q, a*(-1))

#print(L)
#print(R)
ans = 0
for i in range(n):
    a = i+1
    l, r, p = L[i], R[i], P[i]
    ans += (p-l+1)*(r-p+1)*a
print(ans)

Submission status: Accepted

Solution code:
class Bit:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """
        (a0+a1+...+ai < x となる最大の i (存在しない時は -1 ) , その時の a0+a1+...+ai )
        a0+a1+...+ai <= x としたい場合は equal = True
        二分探索であるため、ai>=0 を満たす必要がある
        """
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i+1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i+1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

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

class BitImos:
    def __init__(self, n):
        self.n = n
        self.p = Bit(self.n + 1)
        self.q = Bit(self.n + 1)

    def add(self, s, t, x):
        """ 区間は閉区間 [s,t] で与えられる。原理は Imos法 と同じ。"""
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    def sum(self, s, t):
        """ 半閉区間[s,t)の累積和を与える """
        return self.p.sum(t) + self.q.sum(t) * t - self.p.sum(s) - self.q.sum(s) * s

    def __getitem__(self, s):
        """ 区間加算後の s 番目の要素をO(log N)で取り出す。Imos法だとこの操作にO(N)かかる。"""
        return self.q.sum(s+1)      # sum は半開区間総和なので、s までの和を得るには s+1 としなければならない点に注意

    def __iter__(self):
        """ max(self) で普段 Imos法 でやってることが出来る。"""
        for t in range(self.n):
            yield self.q.sum(t+1)

    def __str__(self):
        text1 = " ".join(["element: "] + list(map(str, self)))
        return text1

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

class BitSet:

    """ 挿入、削除、k番目の値を取得、全てがO(logN)で可能。重複にも対応。"""
    """ 原理的に ai>=0 であるため、二分探索が可能である点も重要　　　　　"""
    def __init__(self, n, A=[]):
        """
        :param n: Aの要素の最大値
        :param A:
        self.size: BitSetに含まれている要素の個数
        """
        self.n = n
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(x, 1)
        self.size += 1
        self.flip += self.size - self.p.sum(x+1)        # 転倒数を使わないなら消してOK

    def remove(self,x):
        self.p.add(x, -1)
        self.size -= 1

    def order(self,x):
        """
        x が小さい順で何番目かを取得（1-indexed)
        BIT.order(x) = bisect_left(BIT.sort(),x) + 1
        BIT.minimum(BIT.order(x)) = BIT.lower_bound(x) = Aに含まれる x 以上の最小の要素
        """
        return self.p.sum(x) + 1

    def bisect_left(self,x):
        if x <= self.n:
            return self.p.sum(x)
        else:
            return self.size

    def bisect_right(self,x):
        x += 1
        if x <= self.n:
            return self.p.sum(x)
        else:
            return self.size

    def flip_counter(self):
        return self.flip

    def count(self,x):
        return self.p[x]

    def minimum(self,k=1):
        """ k 番目に小さい値を取得 （1-indexed）  """
        if k <= self.size:
            return self.p.lower_bound(k)[0] + 1
        else:
            sys.stderr.write("minimum: list index out of range (k={0})\n".format(k))

    def min(self):
        return self.minimum(1)

    def max(self):
        return self.p.lower_bound(self.size)[0] + 1

    def upper_bound(self,x):
        """ x以下の最大の要素の値を返す """
        k = self.p.sum(x+1)
        if k:
            return self.minimum(k)
        else:
            sys.stderr.write("upper_bound: no element smaller than {0} in this BitSet\n".format(x))

    def lower_bound(self,x):
        """ x以上の最小の要素の値を返す """
        k = self.p.sum(x) + 1
        if k <= self.size:
            return self.minimum(k)
        else:
            sys.stderr.write("lower_bound: no element larger than {0} in this BitSet\n".format(x))

    def __getitem__(self, k):
        """ ソートした時の k 番目の要素 (0-indexed)  """
        if k >= 0:
            return self.minimum(k+1)
        else:
            return self.minimum(self.size + 1 + k)

    def __len__(self):
        return self.size

    def __iter__(self):
        for i in range(self.n+1):
            if self.p[i]:
                for _ in range(self.p[i]):
                    yield i

    def __str__(self):
        text1 = " ".join(list(map(str, self)))
        return "[" + text1 + "]"

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


import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
c = dict()
for i, a in enumerate(A,start=1):
    c[a] = i
B = BitSet(N+2)
B.add(0)
B.add(N+1)
res = 0
for a in sorted(A):
    s = c[a]
    b = B.bisect_left(s)
    if b==0:
        res += a*(B[b]-s)
    elif b==len(B):
        res += a*(s-B[b-1])
    else:
        res += a*(s-B[b-1])*(B[b]-s)
    B.add(s)
print(res)

Submission status: Accepted

Solution code:
N = int(input())
A = tuple(map(int,input().split()))

left_amin = [0]*N

stack = [(0,-1)]

for i,a in enumerate(A):
    while stack[-1][0] > a:
        stack.pop()
    left_amin[i] = stack[-1][1]
    stack.append((a,i))

right_amin = [0]*N

stack = [(0,N)]

for i,a in zip(reversed(range(N)),reversed(A)):
    while stack[-1][0] > a:
        stack.pop()
    right_amin[i] = stack[-1][1]
    stack.append((a,i))


res = 0

for i,(l,r,a) in enumerate(zip(left_amin,right_amin,A)):
    res += a*(i-l)*(r-i)
print(res)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
l = [i-1 for i in range(n+2)]
r = [i+1 for i in range(n+2)]
ind = [0]*n

for i,a in enumerate(A):
    ind[a-1] = i

ans = 0
for i in range(n-1,-1,-1):
    x = ind[i]
    ans += (i+1)*(r[x]-x)*(x-l[x])
    l[r[x]],r[l[x]], = l[x],r[x]
print(ans)

Submission status: Accepted

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

left = [0] * (N + 1)
right = [0] * (N + 1)

# 左から
buf = list()
for i in range(N):
    while len(buf) > 0 and a[buf[-1]] > a[i]:
        buf.pop()
    if len(buf) > 0:
        left[i] = buf[-1]
    else:
        left[i] = -1
    buf.append(i)

# 右から
buf = list()
for i in reversed(range(N)):
    while len(buf) > 0 and a[buf[-1]] > a[i]:
        buf.pop()
    if len(buf) > 0:
        right[i] = buf[-1]
    else:
        right[i] = N
    buf.append(i)

ans = 0
for i in range(N):
    ans += a[i] * (i - left[i]) * (right[i] - i)

print(ans)

Submission status: Accepted

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

# indexをソート
b = [0] * N
for i in range(N):
    b[a[i] - 1] = i

# 初期化　端っこ対策としてひとつ余計に取っている
left = [0] * (N + 1)
right = [0] * (N + 1)
for i in range(N + 1):
    left[i] = i-1
    right[i] = i+1

# 更新
for idx in reversed(b):
    left[right[idx]] = left[idx]
    right[left[idx]] = right[idx]

ans = 0
for i in range(N):
    ans += a[i] * (i - left[i]) * (right[i] - i)

print(ans)