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

Solution code:
1 / (not ' ' in input())
1 / (not '  ' in input())

Submission status: Wrong Answer

Solution code:
input()
1 / (not '  ' in input())

Submission status: Wrong Answer

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

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, c
cdef iterator it, jt
cdef vector[int] a = [*map(int, input().split())]
cdef vector[int] l = [0] * n
for i in range(n): l[a[i] - 1] = i
cdef set[int] s = set[int]([-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: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    ans = 0
    for i, a in enumerate(A):
        l = r = i
        while l >= 0 and A[l] >= a: l -= 1
        while r < N and A[r] >= a: r += 1
        print(i, a, l, r)
        ans += a * (i - l) * (r - i)
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
n = int(input())
aa = list(map(int, input().split()))
print(0)

Submission status: Wrong Answer

Solution code:
# B - Minimum Sum
N = int(input())
A = list(enumerate(list(map(int,input().split()))))
left = [i-1 for i in range(N)]
right = [i+1 for i in range(N)]
A.sort(key=lambda x:x[1],reverse=True)
ans = 0
for i,a in A:
    il,ir = left[i],right[i]
    ans += a*(i-il)*(ir-i)
    if ir<N:
        left[ir] = il
    if il>0:
        right[il] = ir
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
x = sorted(set(a))
if (max(a) - 1) // 2 + 1 == min(a):
  if max(a) & 1:
    m = m = a.count(x[0]) != 2
    for i in range(x[0],x[-1]+1):
      if a.count(i) < 2: m = 1
    if m:
      print("Impossible")
    else:
      print("Possible")
  else:
    m = a.count(x[0]) != 1
    for i in range(x[0]+1,x[-1]+1):
      if a.count(i) < 2: m = 1
    if m:
      print("Impossible")
    else:
      print("Possible")
else:
  print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

n, *aaa = map(int, sys.stdin.buffer.read().split())
aaa_with_index = list(enumerate(aaa, start=1))
aaa_with_index.sort(key=itemgetter(1), reverse=True)
left = list(range(n + 2))
right = left.copy()
ans = 0
for i, a in aaa_with_index:
    li = left[i]
    ri = right[i]
    ans += a * (i - li + 1) * (ri - i + 1)
    left[right[i + 1]] = li
    right[left[i - 1]] = ri

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n=int(input())
n+=3
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num

l=list(map(int,input().split()))
p=[]

n-=3
for i in range(n):
    p.append([l[i],i+1])
p.sort(key=lambda x:x[0])
ans=0
update(0,1)
update(n+1,1)
for i in range(n):
    update(p[i][1],1)
    x=query(0,p[i][1]+1)
    ok=n+2
    ng=-1
    while ok-ng>1:
        m=(ok+ng)//2
        if query(0,m)<x-1:
            ng=m
        else:
            ok=m
    left=ok
    continue
    ok=n+2
    ng=-1
    while ok-ng>1:
        m=(ok+ng)//2
        if query(0,m)<x+1:
            ng=m
        else:
            ok=m
    right=ng
    ans+=(i+1)*(p[i][1]-left+1)*(right-p[i][1])
    #print(left,p[i][1],right)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

scan = sys.stdin.readline


n = int(scan().rstrip())
a = [int(_) for _ in scan().rstrip().split()]

s = 0
min_arr = [0]*n

for i in range(n):
  a_i = a[i]
  for j in range(i):
    if min_arr[j] > a_i:
      min_arr[j] = a_i
    s += min_arr[j]

print(s)

Submission status: Wrong Answer

Solution code:
import sys

scan = sys.stdin.readline


n = int(scan().rstrip())
a = [int(_) for _ in scan().rstrip().split()]

s = 0
min_arr = [0]*n

for i in range(n):
  a_i = a[i]
  for j in range(i):
    if min_arr[j] > a_i:
      min_arr[j] = a_i
    s = min_arr[j]

print(s)

Submission status: Wrong Answer

Solution code:
import sys

scan = sys.stdin.readline


n = int(scan().rstrip())
a = [int(_) for _ in scan().rstrip().split()]

s = 0

for i in range(n):
  cur_min = a[i]
  for j in range(i, n):
    if cur_min > a[j]:
      cur_min = a[j]
    s += cur_min

print(cur_min)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

# 大きい数字から追加していく。そのときの連結成分の大きさだけ足される。
# union findっぽく。各成分の左端を根として持つ

N = int(input())
A = [int(x) for x in input().split()]

x_to_i = {x:i for i,x in enumerate(A)}

V = set()
root = dict()
size = dict()

def find_root(x):
    y = root[x]
    if x == y:
        return y
    ry = root[y]
    root[x] = ry
    return ry

def merge(x,y):
    rx = find_root(x)
    ry = find_root(y)
    sx = size[rx]
    sy = size[ry]
    if sx > sy:
        rx,ry = ry,rx
        sx,sy = sy,sx
    root[rx] = ry
    size[ry] += sx

answer = 0
for x in range(N,0,-1):
    i = x_to_i[x]
    V.add(i)
    size[i] = 1
    root[i] = i
    left = 0
    right = 0
    if i-1 in V:
        left = size[find_root(i-1)]
        merge(i-1,i)
    if i+1 in V:
        right = size[find_root(i+1)]
        merge(i+1,i)
    cnt = (left+1) * (right+1)
    answer += x * cnt

print(answer)

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=0
arr=[0]
arr+=list(map(int,input().split()))
arr+=[0]
tl=[0]
tmp=0
for i in range(1,n+1):
  if arr[i-1]>arr[i]:
    tmp+=1
  else:
    tmp=0
  tl.append(tmp)
tr=[0]
tmp=0
for i in range(n,0,-1):
  if arr[i+1]>arr[i]:
    tmp+=1
  else:
    tmp=0
  tr.append(tmp)
for i in range(1,n+1):
  ans+=arr[i]*(tl[i]+1)*(tr[i]+1)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
idx=[0]*N
for i,a in enumerate(A):
    idx[a-1]=i
inf=N+1
L=1
while L<N:
    L*=2
A=A+(L-len(A))*[inf]
seg=[inf]*(2*L-1)
K=2*L-1
def renew(k,l,r):
    global seg
    if K-L<=k<K:
        seg[k]=A[k-L+1]
        return
    else:
        renew(2*k+1,l,(l+r)//2)
        renew(2*k+2,(l+r)//2,r)
        seg[k]=min(seg[2*k+1],seg[2*k+2])
        return
renew(0,0,L)
def up(i,x,k,l,r):
    if seg[(k-1)//2]==x:
        if k==0:
            return k,l,r
        if k%2==1:
            r=r+r-l
        elif k%2==0:
            l=l-r+l
        return up(i,x,(k-1)//2,l,r)
    else:
        return k,l,r
def downleft(i,x,k,l,r,b,e):
    if seg[k]<x:
        if K-L<=k<K:
            return b,e
        if seg[2*k+2]<x:
            b,e=downleft(i,x,2*k+2,(l+r)//2,r,b,e)
            return b,e
        else:
            b,e=min(b,(l+r)//2),e
        if seg[2*k+1]<x:
            b,e=downleft(i,x,2*k+1,l,(l+r)//2,b,e)
        return b,e
    elif seg[k]>x:
        return min(b,l),e
    return b,e
def downright(i,x,k,l,r,b,e):
    if seg[k]<x:
        if K-L<=k<K:
            return b,e
        if seg[2*k+1]<x:
            b,e=downright(i,x,2*k+1,l,(l+r)//2,b,e)
            return b,e
        else:
            b,e=b,max((l+r)//2,e)
        if seg[2*k+2]<x:
            b,e=downright(i,x,2*k+2,(l+r)//2,r,b,e)
        return b,e
    elif seg[k]>x:
        return b,max(r,e)
    return b,e
ans=0
for i in range(N):
    k,l,r=up(idx[i],i+1,idx[i]+L-1,idx[i],idx[i]+1)
    if l>0:
        bl,br=downleft(idx[i],i+1,k-1,l-r+l,l,l,l)
    else:
        bl=l
    if r<L:
        el,er=downright(idx[i],i+1,k+1,r,r+r-l,r,r)
    else:
        er=L
    er=min(er,N)
    ans+=(i+1)*(idx[i]-bl+1)*(er-idx[i])
print(ans)

Submission status: Wrong Answer

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

l=[]
r=[]
s=[]

for i,x in enumerate(a):
  left=i
  if len(s)>0 and x<s[-1][0]:
    left=s[-1][-1]
    s.pop()
  l.append(left)
  s.append([x,left])
  #print(l)
  #print(s)
s=[]
for i in range(N-1,-1,-1):
  right=i
  x=a[i]
  if len(s)>0 and x<s[-1][0]:
    right=s[-1][-1]
    s.pop()
  r.append(right)
  s.append([x,right])
r=r[::-1]
ans=0
for i,(x,le,ri) in enumerate(zip(a,l,r)):
  ans+=x*(i-le+1)*(ri-i+1)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())
A=list(map(int,input().split()))

A=[N+1]+A+[0]

for i in range(len(A)):
    A[i]=5-A[i]

ans=0
for i in range(1,N+1):
    R=bisect.bisect_left(A[i:],A[i])
    L=bisect.bisect_right(A[:i+1],A[i])
    ans+=L*R
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
d = {}
for i,j in enumerate(a):
    d[j] = i

uf = [-1]*n
def root(a):
    if uf[a] < 0:
        return a
    uf[a] = root(uf[a])
    return uf[a]
def unite(a,b):
    ra,rb = root(a),root(b)
    if ra==rb:
        return False
    if uf[ra] > uf[rb]:
        ra,rb = rb,ra
    uf[ra] += uf[rb]
    uf[rb] = ra
    return True

ans = 0
for i in range(n,0,-1):
    left=right=0
    ind = d[i]

    if ind<n-1 and a[ind] < a[ind+1]:
        right -= uf[ind+1]
        unite(ind, ind+1)
    if ind>0 and a[ind] < a[ind-1]:
        left -= uf[ind-1]
        unite(ind, ind-1)
    ans += i*(left+1)*(right+1)

print(ans)

Submission status: Wrong Answer

Solution code:
from numpy import*
n=int(input())
b=array([0,n+1])
c=0
for i,v in enumerate(argsort(input().split())+1,1):
  j=searchsorted(b,v)
  c+=(b[j]-v)*(v-b[j-1])*i
  b=insert(b,j,v)
print(c)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A):
        idxs[a] = i
    ll = list(range(N + 1))
    rr = list(range(N + 1))
    ans = 0
    for a in range(N, 0, -1):
        idx = idxs[a]
        l, r = ll[idx], rr[idx]
        ans += (idx - l + 1) * (r - idx + 1) * a
        ll[idx + 1] = l
        rr[idx - 1] = r

    return ans

print(main())

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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


def dfs(l):
    ret = 0
    if len(l) == 1:
        return l[0]
    elif len(l) == 0:
        return 0
    else:
        le = len(l)
        mi = min(l)
        min_ind = l.index(mi)
        ret += mi*(min_ind+1)*(le-min_ind)
        return ret + dfs(l[:min_ind])+dfs(l[min_ind+1:])


ans = dfs(A)
print(ans)
print(0)

Submission status: Wrong Answer

Solution code:
class Avltree:
    def __init__(self,key=None):
        self.key = key
        self.left = None
        self.right = None 
        self.balance = "Even"

    def search_lower(self,key,key_lower,key_higher):
        if self.key == None:
            return [key_lower,key_higher]
        if self.key > key:
            key_higher = self.key
            if self.left == None:
                return [key_lower,key_higher]
            else:
                return self.left.search_lower(key,key_lower,key_higher)
        if self.key < key:
            key_lower = self.key
            if self.right == None:
                return [key_lower,key_higher]
            else:
                return self.right.search_lower(key,key_lower,key_higher)
        #self.key == keyの場合
        if self.left == None and self.right == None:
            return [key_lower,key_higher]
        if self.left == None:
            if key_higher == None:
                key_higher = 10**6
            return [key_lower,min(key_higher,self.right.end_lower(self.right.key))]
        if self.right == None:
            if key_lower == None:
                key_lower = -10**6
            return [max(key_lower,self.left.end_higher(self.left.key)),key_higher]
        
        if key_lower == None:
            key_lower = -10**6
        if key_higher == None:
            key_higher = 10**6    
        return [max(key_lower,self.left.end_higher(self.left.key)),min(key_higher,self.right.end_lower(self.right.key))]
        
    
    def end_lower(self,end_lower_key):
        if self.left == None:
            return end_lower_key
        else:
            end_lower_key = self.left.key
            return self.left.end_lower(end_lower_key)
    def end_higher(self,end_higher_key):
        if self.right == None:
            return end_higher_key
        else:
            end_higher_key = self.right.key
            return self.right.end_higher(end_higher_key)
    
            
    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self,p,v): # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else :
            p.right = v 
    def insert(self,key): # rootでのみ呼ばれる挿入
        if self.key == None: # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self,key)
        elif key > self.key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self,key)
        else: # key == self.key:
            pass # do not overwrite
    def insertx(self,p,key): # replaceを呼ぶために一つ上の親を持っているinsert
        if self.key > key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                if not self.left.insertx(self, key): # 左の木が生長しなければ、
                    return False # 成長しない
            if self.balance == "Right":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Left"
                return True # 成長した
            elif self.balance == "Left":
                if self.left.balance == "Right":
                    self.replace(p,self.DoubleRightRotation())
                elif self.left.balance == "Left":
                    self.replace(p,self.SingleRightRotation())
                return False # rotationを行うと成長しない
        if self.key < key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                if not self.right.insertx(self, key):
                    return False 
            if self.balance == "Left":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Right"
                return True
            elif self.balance == "Right":
                if self.right.balance == "Left": 
                    self.replace(p,self.DoubleLeftRotation())
                elif self.right.balance == "Right":
                    self.replace(p,self.SingleLeftRotation())
                return False
        return False # self.key == keyの時は何もしないので成長もしない 

def inpl(): return [int(i) for i in input().split()]
n = int(input())
a = inpl()
b = {a[i]: i for i in range(n)}

root = Avltree()
ass = 0

for i in range(1,n+1):
    [l,r] = root.search_lower(b[i],-1,n)
    ass += (b[i]-l)*(r-b[i])*i
    root.insert(b[i])
print(1)

Submission status: Wrong Answer

Solution code:

class Avltree:
    def __init__(self,key=None):
        self.key = key
        self.left = None
        self.right = None 
        self.balance = "Even"

    def search_lower(self,key,key_lower,key_higher):
        if self.key == None:
            return [key_lower,key_higher]
        if self.key > key:
            key_higher = self.key
            if self.left == None:
                return [key_lower,key_higher]
            else:
                return self.left.search_lower(key,key_lower,key_higher)
        if self.key < key:
            key_lower = self.key
            if self.right == None:
                return [key_lower,key_higher]
            else:
                return self.right.search_lower(key,key_lower,key_higher)
        #self.key == keyの場合
        if self.left == None and self.right == None:
            return [key_lower,key_higher]
        if self.left == None:
            if key_higher == None:
                key_higher = 10**6
            return [key_lower,min(key_higher,self.right.end_lower(self.right.key))]
        if self.right == None:
            if key_lower == None:
                key_lower = -10**6
            return [max(key_lower,self.left.end_higher(self.left.key)),key_higher]
        
        if key_lower == None:
            key_lower = -10**6
        if key_higher == None:
            key_higher = 10**6    
        return [max(key_lower,self.left.end_higher(self.left.key)),min(key_higher,self.right.end_lower(self.right.key))]
        
    
    def end_lower(self,end_lower_key):
        if self.left == None:
            return end_lower_key
        else:
            end_lower_key = self.left.key
            return self.left.end_lower(end_lower_key)
    def end_higher(self,end_higher_key):
        if self.right == None:
            return end_higher_key
        else:
            end_higher_key = self.right.key
            return self.right.end_higher(end_higher_key)
    
            
    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self,p,v): # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else :
            p.right = v 
    def insert(self,key): # rootでのみ呼ばれる挿入
        if self.key == None: # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self,key)
        elif key > self.key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self,key)
        else: # key == self.key:
            pass # do not overwrite
    def insertx(self,p,key): # replaceを呼ぶために一つ上の親を持っているinsert
        if self.key > key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                if not self.left.insertx(self, key): # 左の木が生長しなければ、
                    return False # 成長しない
            if self.balance == "Right":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Left"
                return True # 成長した
            elif self.balance == "Left":
                if self.left.balance == "Right":
                    self.replace(p,self.DoubleRightRotation())
                elif self.left.balance == "Left":
                    self.replace(p,self.SingleRightRotation())
                return False # rotationを行うと成長しない
        if self.key < key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                if not self.right.insertx(self, key):
                    return False 
            if self.balance == "Left":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Right"
                return True
            elif self.balance == "Right":
                if self.right.balance == "Left": 
                    self.replace(p,self.DoubleLeftRotation())
                elif self.right.balance == "Right":
                    self.replace(p,self.SingleLeftRotation())
                return False
        return False # self.key == keyの時は何もしないので成長もしない 


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

def inpl(): return [int(i) for i in input().split()]
n = int(input())
a = inpl()
b = {a[i]: i for i in range(n)}

root = Avltree()
ass = 0

for i in range(1,n+1):
    [l,r] = root.search_lower(b[i],-1,n)
    ass += (b[i]-l)*(r-b[i])*i
    root.insert(b[i])
print(1)