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())
  p = list(map(int, input().split()))
  dn = {x: i for i, x in enumerate(p)}
  
  
  #####segfunc#####
  def segfunc(x, y):
      return x + y
  
  
  #################
  
  #####ide_ele#####
  ide_ele = 0
  #################
  
  
  class SegTree:
      """
      init(init_val, ide_ele): 配列init_valで初期化 O(N)
      update(k, x): k番目の値をxに更新 O(logN)
      query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
      """
  
      def __init__(self, init_val, segfunc=segfunc, ide_ele=ide_ele):
          """
          init_val: 配列の初期値
          segfunc: 区間にしたい操作
          ide_ele: 単位元
          n: 要素数
          num: n以上の最小の2のべき乗
          tree: セグメント木(1-index)
          """
          n = len(init_val)
          self.segfunc = segfunc
          self.ide_ele = ide_ele
          self.num = 1 << (n - 1).bit_length()
          self.tree = [ide_ele] * 2 * self.num
          # 配列の値を葉にセット
          for i in range(n):
              self.tree[self.num + i] = init_val[i]
          # 構築していく
          for i in range(self.num - 1, 0, -1):
              self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
  
      def update(self, k, x):
          """
          k番目の値をxに更新
          k: index(0-index)
          x: update value
          """
          k += self.num
          self.tree[k] = x
          while k > 1:
              self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
              k >>= 1
  
      def query(self, l, r):
          """
          [l, r)のsegfuncしたものを得る
          l: index(0-index)
          r: index(0-index)
          """
          res = self.ide_ele
  
          l += self.num
          r += self.num
          while l < r:
              if l & 1:
                  res = self.segfunc(res, self.tree[l])
                  l += 1
              if r & 1:
                  res = self.segfunc(res, self.tree[r - 1])
              l >>= 1
              r >>= 1
          return res
  
  
  st = SegTree([0] * n)
  ans = 0
  
  for k in range(1, n + 1):
      i = dn[k]
      # idx=iを含み、区間和が0になる最長の区間を調べる。
      l, r = 0, i
      while r - l > 1:
          x = (l + r) // 2
          if st.query(x, i + 1) > 0:
              l, r = x, r
          else:
              l, r = l, x
      l0 = l if st.query(l, i + 1) == 0 else r
      l, r = i, n - 1
      while r - l > 1:
          x = (l + r) // 2
          if st.query(i, x + 1) > 0:
              l, r = l, x
          else:
              l, r = x, r
      r0 = r if st.query(i, r + 1) == 0 else l
      ans += k * (i - l0 + 1) * (r0 - i + 1)
      st.update(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"}]