output_description: Print the number of possible passwords.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: import sys
  
  
  def input():
      return sys.stdin.readline()[:-1]
  
  
  class SegmentTree:
      def __init__(self, L, op, ide):
          self.op = op
          self.ide = ide
          self.sz = len(L)
          self.n = 1
          self.s = 1
          for i in range(1000):
              self.n *= 2
              self.s += 1
              if self.n >= self.sz:
                  break
          self.node = [self.ide] * (2 * self.n - 1)
  
          for i in range(self.sz):
              self.node[i + self.n - 1] = L[i]
  
          for i in range(self.n - 2, -1, -1):
              self.node[i] = self.op(self.node[i * 2 + 1], self.node[i * 2 + 2])
  
      def add(self, a, x):
          k = a + self.n - 1
          self.node[k] += x
          for i in range(1000):
              k = (k - 1) // 2
              self.node[k] = self.op(self.node[2 * k + 1], self.node[2 * k + 2])
              if k <= 0:
                  break
  
      def substitute(self, a, x):
          k = a + self.n - 1
          self.node[k] = x
          for i in range(1000):
              k = (k - 1) // 2
              self.node[k] = self.op(self.node[2 * k + 1], self.node[2 * k + 2])
              if k <= 0:
                  break
  
      def get_one(self, a):
          k = a + self.n - 1
          return self.node[k]
  
      def get(self, l, r):
          res = self.ide
          n = self.n
          if self.sz <= r or 0 > l:
              print("ERROR: the indice are wrong.")
              return False
  
          for i in range(self.s):
              count = 2**i - 1
              a = (r + 1) // n
              b = (l - 1) // n
              if a - b == 3:
                  res = self.op(self.node[count + b + 1], res)
                  res = self.op(self.node[count + b + 2], res)
                  right = a * n
                  left = (b + 1) * n - 1
                  break
              if a - b == 2:
                  res = self.op(self.node[count + b + 1], res)
                  right = a * n
                  left = (b + 1) * n - 1
                  break
              n = n // 2
  
          # left
          n1 = n // 2
          for j in range(i + 1, self.s):
              count = 2**j - 1
              a = (left + 1) // n1
              b = (l - 1) // n1
              if a - b == 2:
                  res = self.op(self.node[count + b + 1], res)
                  left = (b + 1) * n1 - 1
              n1 = n1 // 2
  
          # right
          n1 = n // 2
          for j in range(i + 1, self.s):
              count = 2**j - 1
              a = (r + 1) // n1
              b = (right - 1) // n1
              if a - b == 2:
                  res = self.op(self.node[count + b + 1], res)
                  right = a * n1
              n1 = n1 // 2
          return res
  
  
  def main():
  
      N = int(input())
      P = list(map(int, input().split()))
  
      ST = SegmentTree(P, max, -(10**27))
  
      def bisect(i, j, ST, num, index, P, Smin, Smin_rev, left_flag):
          if left_flag:
              if i == j:
                  if P[i] > num:
                      return i
                  else:
                      return i - 1
  
              if Smin[j + 1] == num:
                  return -1
              if P[j] > num:
                  return j
          else:
              if i == j:
                  if P[i] > num:
                      return i
                  else:
                      return i + 1
  
              if Smin_rev[i - 1] == num:
                  return N
              if P[i] > num:
                  return i
  
          if not left_flag:
              while j - i > 1:
                  if ST.get(index + 1, (i + j) // 2) < num:
                      i = (i + j) // 2
                  else:
                      j = (i + j) // 2
              return j
          else:
              while j - i > 1:
                  if ST.get((i + j) // 2, index - 1) < num:
                      j = (i + j) // 2
                  else:
                      i = (i + j) // 2
              return i
  
      Smin = []
      smin = -(10**27)
      for i in range(N):
          smin = max(smin, P[i])
          Smin.append(smin)
  
      Smin_rev = []
      smin = -(10**27)
      for i in range(N):
          smin = max(smin, P[N - i - 1])
          Smin_rev.append(smin)
      Smin_rev = Smin_rev[::-1]
  
      score = 0
  
      for i in range(N):
          if i == 0:
              right1 = bisect(i + 1, N - 1, ST, P[i], i, P, Smin, Smin_rev, False)
              if right1 >= N - 1:
                  right2 = N
              else:
                  right2 = bisect(
                      right1 + 1, N - 1, ST, P[i], right1, P, Smin, Smin_rev, False
                  )
              right1, right2 = right1 - i, right2 - i
              left1 = 1
              left2 = 1
  
          elif i == N - 1:
              left1 = bisect(0, i - 1, ST, P[i], i, P, Smin, Smin_rev, True)
              if left1 <= 0:
                  left2 = -1
              else:
                  left2 = bisect(0, left1 - 1, ST, P[i], left1, P, Smin, Smin_rev, True)
              left1, left2 = i - left1, i - left2
              right1 = 1
              right2 = 1
          else:
              right1 = bisect(i + 1, N - 1, ST, P[i], i, P, Smin, Smin_rev, False)
              if right1 >= N - 1:
                  right2 = N
              else:
                  right2 = bisect(
                      right1 + 1, N - 1, ST, P[i], right1, P, Smin, Smin_rev, False
                  )
              right1, right2 = right1 - i, right2 - i
  
              left1 = bisect(0, i - 1, ST, P[i], i, P, Smin, Smin_rev, True)
              if left1 <= 0:
                  left2 = -1
              else:
                  left2 = bisect(0, left1 - 1, ST, P[i], left1, P, Smin, Smin_rev, True)
              left1, left2 = i - left1, i - left2
  
          score += (left1 * (right2 - right1) + (left2 - left1) * right1) * P[i]
      print(score)
  
  
  main()
  
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."}]