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: import random
  import time
  
  # Treap
  
  
  # d = 0: right rotation
  # d = 1: left rotation
  def rotate(nd, d):
      c = nd[d]
      if d:
          e = c[1]
          nd[1] = c[0]
          c[0] = nd
      else:
          e = c[0]
          nd[0] = c[1]
          c[1] = nd
  
      r = c[4] = nd[4]
      nd[4] = r - (e[4] if e else 0) - 1
      return c
  
  
  # insert a node with key = val and priority = pri
  root = None
  
  
  def insert(val, pri):
      global root
      st = []
      dr = []
      x = root
      while x:
          st.append(x)
          if x[2] == val:
              return
          d = x[2] < val
          dr.append(d)
          x = x[d]
  
      # [<left>, <right>, <key>, <priority>, <count>]
      nd = [None, None, val, pri, 1]
      while st:
          x = st.pop()
          d = dr.pop()
          x[d] = nd
          x[4] += 1
          if x[3] >= nd[3]:
              break
          rotate(x, d)
      else:
          root = nd
  
      for x in st:
          x[4] += 1
  
  
  def __delete(nd):
      st = []
      dr = []
      while nd[0] or nd[1]:
          l = nd[0]
          r = nd[1]
          d = (l[3] <= r[3]) if l and r else (l is None)
          st.append(rotate(nd, d))
          dr.append(d ^ 1)
      nd = x = None
      while st:
          nd = x
          x = st.pop()
          d = dr.pop()
          x[d] = nd
          x[4] -= 1
      return x
  
  
  def delete(val):
      global root
      x = root
  
      st = []
      y = None
      while x:
          if val == x[2]:
              break
          y = x
          d = x[2] < val
          st.append(y)
          x = x[d]
      else:
          return
  
      if y:
          y[d] = __delete(x)
          for x in st:
              x[4] -= 1
      else:
          root = __delete(x)
  
  
  def find(val):
      global root
      x = root
      while x:
          if val == x[2]:
              return 1
          x = x[x[2] < val]
      return 0
  
  
  def search1(val):
      global root
      x = root
      ans = -1
      while x:
          if val == x[2]:
              return val
          if val > x[2]:
              ans = max(ans, x[2])
              if x[1] == None:
                  return ans
              else:
                  x = x[1]
          if val < x[2]:
              if x[0] == None:
                  return ans
              else:
                  x = x[0]
      return ans
  
  
  def search2(val):
      global root
      x = root
      ans = 10**20
      while x:
          if val == x[2]:
              return val
          if val > x[2]:
              if x[1] == None:
                  return ans
              else:
                  x = x[1]
          if val < x[2]:
              ans = min(ans, x[2])
              if x[0] == None:
                  return ans
              else:
                  x = x[0]
      return ans
  
  
  N = int(input())
  A = list(map(int, input().split()))
  A = [A[i] - 1 for i in range(0, N)]
  function = [0 for i in range(0, N)]
  for i in range(0, N):
      function[A[i]] = i
  
  random.seed()
  randint = random.randint
  
  insert(function[0], randint(1, 200000))
  data1 = [0 for i in range(0, N)]
  data2 = [0 for i in range(0, N)]
  data1[0] = -1
  data2[0] = N
  for i in range(1, N):
      if search1(function[i]) != -1:
          data1[i] = search1(function[i])
      else:
          data1[i] = -1
      if search2(function[i]) != 10**20:
          data2[i] = search2(function[i])
      else:
          data2[i] = N
      insert(function[i], randint(1, 200000))
  
  ans = 0
  for i in range(0, N):
      prod = (function[i] - data1[i]) * (data2[i] - function[i])
      ans += prod * (i + 1)
  
  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"}]