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 getlist():
      return list(map(int, input().split()))
  
  
  class Node:
      def __init__(self, key, parent=None, left=None, right=None):
          self.key = key
          self.p = parent
          self.left = left
          self.right = right
  
      def __repr__(self):
          return "Node(%s)" % repr(self.key)
  
      def search(self, k):
          if self is None or k == self.key:
              return self
          if k < self.key:
              return self.left.search(k)
          else:
              return self.right.search(k)
  
      def minimum(self):
          minimum = self
          while minimum.left:
              minimum = minimum.left
          return minimum
  
      def maximum(self):
          while self.right:
              self = self.right
          return self
  
      # 次節点
      def successor(self):
          if self.right:
              return self.right.minimum()
          y = self.p
          while y and self == y.right:
              self = y
              y = y.p
          return y
  
      # 前節点
      def predecessor(self):
          if self.left:
              return self.left.maximum()
          y = self.p
          while y and self == y.left:
              self = y
              y = y.p
          return y
  
      # 二分探索木のルートを返すメソッド
      def root(self):
          while self.p:
              self = self.p
          return self
  
      # 挿入
      def insert(self, value):
          z = Node(value)
          y = None
          self = self.root()
          while self:
              y = self
              if z.key < self.key:
                  self = self.left
              else:
                  self = self.right
          z.p = y
          if y is None:
              pass
          elif z.key < y.key:
              y.left = z
          else:
              y.right = z
  
  
  N = int(input())
  a = getlist()
  l = [0] * (N + 1)
  for i in range(1, N + 1):
      l[a[i - 1]] = i
  
  
  ans = 0
  DD = Node(N + 1)
  DD.insert(0)
  
  for i in range(1, N + 1):
      val = l[i]
      DD.insert(val)
      ans += (
          i
          * (DD.search(val).successor().key - val)
          * (val - DD.search(val).predecessor().key)
      )
  
  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"}]