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: def main():
    class Avltree:
      def __init__(self,key=None):
          self.key = key
          self.left = None
          self.right = None 
          self.balance = "Even"
      def search(self,key):
          if self.key == None:
              return None
          if self.key > key:
              if self.left == None:
                  return None
              else:
                  return self.left.search(key)
          if self.key < key:
              if self.right == None:
                  return None
              else:
                  return self.right.search(key)
          return self
          
      def search_lower(self,key,key_lower):
          if self.key == None:
              return key_lower
          if self.key > key:
              if self.left == None:
                  return key_lower
              else:
                  return self.left.search_lower(key,key_lower)
          if self.key < key:
              key_lower = self.key
              if self.right == None:
                  return key_lower
              else:
                  return self.right.search_lower(key,key_lower)
          if self.left == None:
              return key_lower
          else:
              if key_lower == None:
                  return self.left.end_higher(self.left.key)
              else:
                  return max(key_lower,self.left.end_higher(self.left.key))
      
      def search_higher(self,key,key_higher):
          if self.key == None:
              return key_higher
          if self.key > key:
              key_higher = self.key
              if self.left == None:
                  return key_higher
              else:
                  return self.left.search_higher(key,key_higher)
          if self.key < key:
              if self.right == None:
                  return key_higher
              else:
                  return self.right.search_higher(key,key_higher)
          if self.right == None:
              return key_higher
          else:
              if key_higher == None:
                  return self.right.end_lower(self.right.key)
              else:
                  return 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
          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 == None:
              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):
          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
          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
  
      def to_s(self):
          return self.key
      def left_s(self):
          if self.left == None:
              return None
          return (self.left).key
      def right_s(self):
          if self.right == 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()
   root.insert(-1)
   root.insert(n)
   for i in range(n):
     root.insert(l[i])
     ans+=(i+1)*(l[i]-root.search_lower(l[i],None))*(root.search_higher(l[i],None)-l[i])
   print(ans)
  if __name__ == '__main__':
      main()
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"}]