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 sys
  
  sys.setrecursionlimit(10000000)
  MOD = 10**9 + 7
  INF = 10**15
  
  
  class SegmentTree:
  
      def __init__(self, N, f, unit):
          self.f = f
          self.unit = unit
          self.N = N
          self.tree = [self.unit] * (2 * self.N)
          # self._build(array)
  
      def _build(self, array):
          for i, x in enumerate(array, self.N):
              self.tree[i] = x
          for i in range(self.N - 1, 0, -1):
              self.tree[i] = self.f(self.tree[i << 1], self.tree[i << 1 | 1])
  
      def update(self, k, x):
          k += self.N
          self.tree[k] = x
          while k > 1:
              k >>= 1
              self.tree[k] = self.f(self.tree[k << 1], self.tree[k << 1 | 1])
  
      def query(self, l, r):
          l += self.N
          r += self.N
          vl = self.unit
          vr = self.unit
          while l < r:
              if l & 1:
                  vl = self.f(vl, self.tree[l])
                  l += 1
              if r & 1:
                  r -= 1
                  vr = self.f(self.tree[r], vr)
              l >>= 1
              r >>= 1
          return self.f(vl, vr)
  
      def debug(self):
          print(self.tree)
  
  
  def main():
      N = int(input())
      A = list(map(int, input().split()))
  
      st = SegmentTree(N, max, -1)
      L = [-1] * N
      for i, a in enumerate(A):
          L[i] = st.query(0, a - 1)
          st.update(a - 1, i)
  
      st = SegmentTree(N, min, N)
      R = [N] * N
      for i in range(N - 1, -1, -1):
          R[i] = st.query(0, A[i] - 1)
          st.update(A[i] - 1, i)
  
      ans = sum((R[i] - i) * (i - L[i]) * A[i] for i in range(N))
      print(ans)
  
  
  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"}]