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: # -*- coding: utf-8 -*-
  import sys
  
  # sys.setrecursionlimit(10**6)
  # buff_readline = sys.stdin.buffer.readline
  buff_readline = sys.stdin.readline
  readline = sys.stdin.readline
  
  INF = 2**62 - 1
  
  
  def read_int():
      return int(buff_readline())
  
  
  def read_int_n():
      return list(map(int, buff_readline().split()))
  
  
  def read_float():
      return float(buff_readline())
  
  
  def read_float_n():
      return list(map(float, buff_readline().split()))
  
  
  def read_str():
      return readline().strip()
  
  
  def read_str_n():
      return readline().strip().split()
  
  
  def error_print(*args):
      print(*args, file=sys.stderr)
  
  
  def mt(f):
      import time
  
      def wrap(*args, **kwargs):
          s = time.time()
          ret = f(*args, **kwargs)
          e = time.time()
  
          error_print(e - s, "sec")
          return ret
  
      return wrap
  
  
  class SegmentTree:
      def __init__(self, array, operator, identity_element):
          _len = len(array)
          self.__op = operator
          self.__size = 1 << (_len - 1).bit_length()
          self.__tree = (
              [identity_element] * self.__size
              + array
              + [identity_element] * (self.__size - _len)
          )
          self.__ie = identity_element
  
          for i in range(self.__size - 1, 0, -1):
              self.__tree[i] = operator(self.__tree[i * 2], self.__tree[i * 2 + 1])
  
      def update(self, i, v):
          i += self.__size
          self.__tree[i] = v
          while i:
              i //= 2
              self.__tree[i] = self.__op(self.__tree[i * 2], self.__tree[i * 2 + 1])
  
      def query(self, l, r):
          """[l, r)"""
          l += self.__size
          r += self.__size
          ret = self.__ie
          while l < r:
              if l & 1:
                  ret = self.__op(ret, self.__tree[l])
                  l += 1
              if r & 1:
                  r -= 1
                  ret = self.__op(ret, self.__tree[r])
              l //= 2
              r //= 2
          return ret
  
  
  @mt
  def slv(N, A):
      ai = [(a, i) for i, a in enumerate(A)]
      ai.sort()
  
      lst = SegmentTree([-1] * N, max, -1)
      rst = SegmentTree([N] * N, min, N)
      ans = 0
      for a, i in ai:
          l = lst.query(0, i)
          r = rst.query(i + 1, N)
          ans += (i - l) * (r - i) * a
          lst.update(i, i)
          rst.update(i, i)
      return ans
  
  
  def main():
      N = read_int()
      A = read_int_n()
      print(slv(N, A))
  
  
  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"}]