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: from collections import deque
  n=int(input())
  a=list(map(int,input().split()))
  A=[a[0]+a[0]<a[1]-a[0]>a[1]]+a+[a[-1]+a[-1]<a[-2]-a[-1]>a[-2]]
  valley=0
  peak=1
  dp=deque()
  for i in range(1,n+1):
    if A[i-1]<A[i]>A[i+1]:
      dp.append((i-1,peak))
    elif A[i-1]>A[i]<A[i+1]:
      dp.append((i-1,valley))
  l,lf=dp.popleft()
  r,rf=dp.popleft()
  if lf == peak:
    ans=a[0]
  else:
    ans=a[0]*(r+1)
  for i in range(1,n-1):
    if r == i:
      t,tf=r,rf
      r,rf=dp.popleft()
      if rf == valley:
        ans+=a[i]*(i-l+1)*(r-i+1)
      else:
        ans+=a[i]
    	l,lf=t,tf
    else:
      if lf == valley:
        ans+=a[i]*(r-i+1)
      else:
        ans+=a[i]*(i-l+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"}]