output_description: Print the number of possible passwords.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: import sys
  
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  
  from operator import itemgetter
  from bisect import bisect, insort
  
  
  def solve(n, ppp):
      q = sorted(enumerate(ppp), key=itemgetter(1), reverse=True)
      le = [-1, -1, n - 1, n, n]
      ans = 0
      for i, p in q[1:]:
          l_i = bisect(le, i)
          LL = le[l_i - 2]
          LR = le[l_i - 1]
          RL = le[l_i]
          RR = le[l_i + 1]
          ans += p * ((LR - LL) * (RL - i) + (RR - RL) * (i - LR))
          insort(le, i)
      return ans
  
  
  n = int(readline())
  ppp = list(map(int, readline().split()))
  print(solve(n, ppp))
  
problem_description: Statement
  
  Takahashi is going to set a 3-character password.
  
  How many possible passwords are there if each of its characters must be a
  digit between 1 and N (inclusive)?
samples: [{"input": "2", "output": "8\n    \n\nThere are eight possible passwords: `111`, `112`, `121`, `122`, `211`, `212`,\n`221`, and `222`.\n\n* * *"}, {"input": "1", "output": "1\n    \n\nThere is only one possible password if you can only use one kind of character."}]