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

Find the following:

<image>

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.

Examples

Input

3
2 1 3


Output

9


Input

4
1 3 2 4


Output

19


Input

8
5 4 8 1 2 6 7 3


Output

85
class Avltree:

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

  def search(self,key):
    node=self
    while node is not None:
      if node.key==key:
        return node
      if node.key>key:
        node=node.left
      elif node.key < key:
        node=node.right
    return None

  def search_lower(self, key, key_lower):
    node=self
    if node.key is None:
      return key_lower
    ans=key_lower
    while node is not None:
      if node.key<key:
        if ans<node.key:
          ans=node.key
        node=node.right
      elif node.key>=key:
        node=node.left
    return ans

  def search_higher(self, key, key_higher):
    node=self
    if node.key is None:
      return key_higher
    ans=key_higher
    while node is not None:
      if node.key>key:
        if ans>node.key:
          ans=node.key
        node=node.left
      elif node.key<=key:
        node=node.right
    return ans

  def end_lower(self, end_lower_key):
    node=self
    while node.left is not None:
      node=node.left
    return node.key

  def end_higher(self, end_higher_key):
    node=self
    while node.right is not None:
      node=node.right
    return node.key

  def DoubleRightRotation(self):
    tl=self.left
    self.left=tl.right.right
    tl.right.right=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):
    if p.left==self:
      p.left=v
    else:
      p.right=v

  def insert(self, key):
    if self.key is None:
      self.key=key
      return self
    if key<self.key:
      if self.left is None:
        self.left=Avltree(key)
      else:
        self.left.insertx(self, key)
    elif key>self.key:
      if self.right is None:
        self.right=Avltree(key)
      else:
        self.right.insertx(self, key)
    else:
      pass

  def insertx(self, p, key):
    node=self
    s=[]
    while True:
      if node.key>key:
        s.append((node, -1))
        if node.left is None:
          node.left=Avltree(key)
          node=node.left
          break
        else:
          node=node.left
      elif node.key<key:
        s.append((node, 1))
        if node.right is None:
          node.right=Avltree(key)
          node=node.right
          break
        else:
          node=node.right
    while len(s)!=0:
      node,direct=s.pop()
      if len(s)!=0:
        par=s[-1][0]
      else:
        par=p
      if direct==-1:
        if node.balance=="Right":
          node.balance="Even"
          break
        elif node.balance=="Even":
          node.balance="Left"
        elif node.balance=="Left":
          if node.left.balance=="Right":
            node.replace(par,node.DoubleRightRotation())
          elif node.left.balance=="Left":
            node.replace(par,node.SingleRightRotation())
          break
      elif direct==1:
        if node.balance=="Left":
          node.balance="Even"
          break
        elif node.balance=="Even":
          node.balance="Right"
        elif node.balance=="Right":
          if node.right.balance=="Left":
            node.replace(par,node.DoubleLeftRotation())
          elif node.right.balance=="Right":
            node.replace(par,node.SingleLeftRotation())
          break

  def to_s(self):
    return self.key

  def left_s(self):
    if self.left is None:
      return None
    return (self.left).key

  def right_s(self):
    if self.right is None:
      return None
    return (self.right).key

n=int(input())
a=list(map(int,input().split()))
ans=0
l=[0]*n
for i in range(n):
  l[a[i]-1]=i
root=Avltree()
for i in range(n):
  root.insert(l[i])
  ans+=(i+1)*(l[i]-root.search_lower(l[i],-1))*(root.search_higher(l[i],n)-l[i])
print(ans)