output_description: Print the answer.
  
  Note that the answer may not fit into a 32-bit integer.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N
      a_1 a_2 ... a_N
attempt: class Node:
      def __init__(self, key):
          self.key = key
          self.lch = None
          self.rch = None
          self.bias = 0
          self.size = 1
  
  
  class AVLTree:
      def __init__(self):
          self.root = None
  
      def rotate_left(self, v):
          u = v.rch
  
          u.size = v.size
          v.size -= u.rch.size + 1 if u.rch is not None else 1
  
          v.rch = u.lch
          u.lch = v
          if u.bias == -1:
              u.bias = v.bias = 0
          else:
              u.bias = 1
              v.bias = -1
          return u
  
      def rotate_right(self, v):
          u = v.lch
  
          u.size = v.size
          v.size -= u.lch.size + 1 if u.lch is not None else 1
  
          v.lch = u.rch
          u.rch = v
          if u.bias == 1:
              u.bias = v.bias = 0
          else:
              u.bias = -1
              v.bias = 1
          return u
  
      def rotateLR(self, v):
          u = v.lch
          t = u.rch
  
          t.size = v.size
          v.size -= u.size - (t.rch.size if t.rch is not None else 0)
          u.size -= t.rch.size + 1 if t.rch is not None else 1
  
          u.rch = t.lch
          t.lch = u
          v.lch = t.rch
          t.rch = v
          self.update_bias_double(t)
          return t
  
      def rotateRL(self, v):
          u = v.rch
          t = u.lch
  
          t.size = v.size
          v.size -= u.size - (t.lch.size if t.lch is not None else 0)
          u.size -= t.lch.size + 1 if t.lch is not None else 1
  
          u.lch = t.rch
          t.rch = u
          v.rch = t.lch
          t.lch = v
          self.update_bias_double(t)
          return t
  
      def update_bias_double(self, v):
          if v.bias == 1:
              v.rch.bias = -1
              v.lch.bias = 0
          elif v.bias == -1:
              v.rch.bias = 0
              v.lch.bias = 1
          else:
              v.rch.bias = 0
              v.lch.bias = 0
          v.bias = 0
  
      def add(self, key):
          if self.root is None:
              self.root = Node(key)
              return
  
          v = self.root
          history = []
          while v is not None:
              if key < v.key:
                  history.append((v, 1))
                  v = v.lch
              elif v.key < key:
                  history.append((v, -1))
                  v = v.rch
              else:
                  return
  
          p, pdir = history[-1]
          if pdir == 1:
              p.lch = Node(key)
          else:
              p.rch = Node(key)
  
          while history:
              v, direction = history.pop()
              v.bias += direction
              v.size += 1
  
              new_v = None
              b = v.bias
              if b == 0:
                  break
  
              if b == 2:
                  u = v.lch
                  if u.bias == -1:
                      new_v = self.rotateLR(v)
                  else:
                      new_v = self.rotate_right(v)
                  break
              if b == -2:
                  u = v.rch
                  if u.bias == 1:
                      new_v = self.rotateRL(v)
                  else:
                      new_v = self.rotate_left(v)
                  break
  
          if new_v is not None:
              if len(history) == 0:
                  self.root = new_v
                  return
              p, pdir = history.pop()
              p.size += 1
              if pdir == 1:
                  p.lch = new_v
              else:
                  p.rch = new_v
  
          while history:
              p, pdir = history.pop()
              p.size += 1
  
      def remove(self, key):
          v = self.root
          history = []
          while v is not None:
              if key < v.key:
                  history.append((v, 1))
                  v = v.lch
              elif v.key < key:
                  history.append((v, -1))
                  v = v.rch
              else:
                  break
          else:
              return False
  
          if v.lch is not None:
              history.append((v, 1))
              lmax = v.lch
              while lmax.rch is not None:
                  history.append((lmax, -1))
                  lmax = lmax.rch
  
              v.key = lmax.key
  
              v = lmax
  
          c = v.rch if v.lch is None else v.lch
  
          if history:
              p, pdir = history[-1]
              if pdir == 1:
                  p.lch = c
              else:
                  p.rch = c
          else:
              self.root = c
              return True
  
          while history:
              new_p = None
  
              p, pdir = history.pop()
              p.bias -= pdir
              p.size -= 1
  
              b = p.bias
              if b == 2:
                  if p.lch.bias == -1:
                      new_p = self.rotateLR(p)
                  else:
                      new_p = self.rotate_right(p)
  
              elif b == -2:
                  if p.rch.bias == 1:
                      new_p = self.rotateRL(p)
                  else:
                      new_p = self.rotate_left(p)
  
              elif b != 0:
                  break
  
              if new_p is not None:
                  if len(history) == 0:
                      self.root = new_p
                      return True
                  gp, gpdir = history[-1]
                  if gpdir == 1:
                      gp.lch = new_p
                  else:
                      gp.rch = new_p
                  if new_p.bias != 0:
                      break
  
          while history:
              p, pdir = history.pop()
              p.size -= 1
  
          return True
  
      def member(self, key):
          v = self.root
          while v is not None:
              if key < v.key:
                  v = v.lch
              elif v.key < key:
                  v = v.rch
              else:
                  return True
          return False
  
      def lower_bound(self, key):
          ret = None
          v = self.root
          while v is not None:
              if v.key >= key:
                  if ret is None or ret > v.key:
                      ret = v.key
                  v = v.lch
              else:
                  v = v.rch
          return ret
  
      def upper_bound(self, key):
          ret = None
          v = self.root
          while v is not None:
              if v.key <= key:
                  if ret is None or ret < v.key:
                      ret = v.key
                  v = v.rch
              else:
                  v = v.lch
          return ret
  
      def find_kth_element(self, k):
          v = self.root
          s = 0
          while v is not None:
              t = s + v.lch.size if v.lch is not None else s
              if t == k:
                  return v.key
              elif t < k:
                  s = t + 1
                  v = v.rch
              else:
                  v = v.lch
          return None
  
      def __contains__(self, key):
          return self.member(key)
  
      def __delitem__(self, key):
          return self.remove(key)
  
      def __bool__(self):
          return self.root is not None
  
      def __len__(self):
          return self.root.size if self.root is not None else 0
  
  
  if __name__ == "__main__":
      N = int(input())
      A = [(a, i) for i, a in enumerate(map(int, input().split()))]
      A.sort(reverse=True)
  
      T = AVLTree()
      T.add(-1)
      T.add(N)
  
      ans = 0
      while A:
          a, i = A.pop()
          l = T.upper_bound(i)
          r = T.lower_bound(i)
          ans += a * (r - i) * (i - l)
          T.add(i)
      print(ans)
  
problem_description: Statement
  
  One day, Snuke was given a permutation of length N, a_1, a_2, ..., a_N, from
  his friend.
  
  Find the following:
  
  ![](https://atcoder.jp/img/agc005/520049e1a049bb9810b398b35d7dcb7f.png)
samples: [{"input": "3\n    2 1 3", "output": "9\n    \n\n* * *"}, {"input": "4\n    1 3 2 4", "output": "19\n    \n\n* * *"}, {"input": "8\n    5 4 8 1 2 6 7 3", "output": "85"}]