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: N = int(input())
  A = list(map(int, input().split()))
  idx = [0] * N
  for i, a in enumerate(A):
      idx[a - 1] = i
  inf = N + 1
  L = 1
  while L < N:
      L *= 2
  A = A + (L - len(A)) * [inf]
  seg = [inf] * (2 * L - 1)
  K = 2 * L - 1
  
  
  def renew(k, l, r):
      global seg
      if K - L <= k < K:
          seg[k] = A[k - L + 1]
          return
      else:
          renew(2 * k + 1, l, (l + r) // 2)
          renew(2 * k + 2, (l + r) // 2, r)
          seg[k] = min(seg[2 * k + 1], seg[2 * k + 2])
          return
  
  
  renew(0, 0, L)
  
  
  def up(i, x, k, l, r):
      if seg[(k - 1) // 2] == x:
          if k == 0:
              return k, l, r
          if k % 2 == 1:
              r = r + r - l
          elif k % 2 == 0:
              l = l - r + l
          return up(i, x, (k - 1) // 2, l, r)
      else:
          return k, l, r
  
  
  def downleft(i, x, k, l, r, b, e):
      if seg[k] < x:
          if K - L <= k < K:
              return b, e
          if seg[2 * k + 2] < x:
              b, e = downleft(i, x, 2 * k + 2, (l + r) // 2, r, b, e)
              return b, e
          else:
              b, e = min(b, (l + r) // 2), e
          if seg[2 * k + 1] < x:
              b, e = downleft(i, x, 2 * k + 1, l, (l + r) // 2, b, e)
          return b, e
      elif seg[k] > x:
          return min(b, l), e
      return b, e
  
  
  def downright(i, x, k, l, r, b, e):
      if seg[k] < x:
          if K - L <= k < K:
              return b, e
          if seg[2 * k + 1] < x:
              b, e = downright(i, x, 2 * k + 1, l, (l + r) // 2, b, e)
              return b, e
          else:
              b, e = b, max((l + r) // 2, e)
          if seg[2 * k + 2] < x:
              b, e = downright(i, x, 2 * k + 2, (l + r) // 2, r, b, e)
          return b, e
      elif seg[k] > x:
          return b, max(r, e)
      return b, e
  
  
  ans = 0
  for i in range(N):
      k, l, r = up(idx[i], i + 1, idx[i] + L - 1, idx[i], idx[i] + 1)
      if l > 0:
          bl, br = downleft(idx[i], i + 1, k - 1, l - r + l, l, l, l)
      else:
          bl = l
      if r < L:
          el, er = downright(idx[i], i + 1, k + 1, r, r + r - l, r, r)
      else:
          er = L
      er = min(er, N)
      ans += (i + 1) * (idx[i] - bl + 1) * (er - idx[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"}]