output_description: Print \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      P_1 P_2 \ldots P_N
attempt: import sys
  import random
  
  
  class RandomizedBinarySearchTree:
      def __init__(self, n):
          n += 10
          self.n = n
          self.children = [[0] * n, [0] * n]
          self.values = [0] * n
          self.counts = [0] * n
          self.indices = list(range(n - 2, -1, -1))
          self.root = -1
  
      def merge(self, left_root, right_root):
          children = self.children
          counts = self.counts
          li = left_root
          ri = right_root
          stack = []
          while li != -1 and ri != -1:
              if random.randrange(counts[li] + counts[ri]) < counts[li]:
                  stack.append((li, 1))
                  li = children[1][li]
              else:
                  stack.append((ri, 0))
                  ri = children[0][ri]
  
          i = li if li != -1 else ri
          while stack:
              pi, is_right = stack.pop()
              children[is_right][pi] = i
              counts[pi] = counts[children[0][pi]] + counts[children[1][pi]] + 1
              i = pi
  
          return i
  
      def split(self, root, x):
          i = root
          lefts, rights = self.children
          values = self.values
          counts = self.counts
          l_stack = []
          r_stack = []
          while i != -1:
              if x < values[i]:
                  r_stack.append(i)
                  i = lefts[i]
              else:
                  l_stack.append(i)
                  i = rights[i]
  
          li, ri = -1, -1
          while l_stack:
              pi = l_stack.pop()
              rights[pi] = li
              counts[pi] = counts[lefts[pi]] + counts[li] + 1
              li = pi
          while r_stack:
              pi = r_stack.pop()
              lefts[pi] = ri
              counts[pi] = counts[ri] + counts[rights[pi]] + 1
              ri = pi
  
          return li, ri
  
      def insert(self, x):
          ni = self.indices.pop()
          self.children[0][ni] = self.children[1][ni] = -1
          self.values[ni] = x
          self.counts[ni] = 1
  
          li, ri = self.split(self.root, x)
          self.root = self.merge(self.merge(li, ni), ri)
  
      def delete(self, x):
          li, mri = self.split(self.root, x - 1)
          mi, ri = self.split(mri, x)
  
          if mi == -1:
              self.root = self.merge(li, ri)
              return
  
          self.indices.append(mi)
          self.root = self.merge(li, ri)
          return
  
      def upper_bound(self, x, default=-1):
          i = self.root
          lefts, rights = self.children
          values = self.values
          counts = self.counts
          y = default
          c = counts[i]
          j = 0
          while i != -1:
              if x < values[i]:
                  y = values[i]
                  c = j + counts[lefts[i]]
                  i = lefts[i]
              else:
                  j += counts[lefts[i]] + 1
                  i = rights[i]
          return y, c
  
      def lower_bound(self, x, default=-1):
          i = self.root
          lefts, rights = self.children
          values = self.values
          counts = self.counts
          y = default
          c = counts[i]
          j = 0
          while i != -1:
              if x <= values[i]:
                  y = values[i]
                  c = j + counts[lefts[i]]
                  i = lefts[i]
              else:
                  j += counts[lefts[i]] + 1
                  i = rights[i]
          return y, c
  
      def get_k_th(self, k, default=-1):
          i = self.root
          children = self.children
          values = self.values
          counts = self.counts
          if counts[i] <= k:
              return default
          j = k
          while i != -1:
              left_count = counts[children[0][i]]
              if left_count == j:
                  return values[i]
              elif left_count > j:
                  i = children[0][i]
              else:
                  j -= left_count + 1
                  i = children[1][i]
          return default
  
      def debug_print(self):
          print("Lefts ", self.children[0])
          print("Rights", self.children[1])
          print("Values", self.values)
          print("Counts", self.counts)
          self._debug_print(self.root, 0)
  
      def _debug_print(self, i, depth):
          if i != -1:
              self._debug_print(self.children[0][i], depth + 1)
              print("      " * depth, self.values[i], self.counts[i])
              self._debug_print(self.children[1][i], depth + 1)
  
  
  q = int(input())
  rbst = RandomizedBinarySearchTree(q)
  for line in sys.stdin:
      t, x = map(int, line.split())
      if t == 1:
          rbst.insert(x)
      else:
          y = rbst.get_k_th(x - 1)
          print(y)
          rbst.delete(y)
  
problem_description: Statement
  
  Given is a permutation P of \\{1, 2, \ldots, N\\}.
  
  For a pair (L, R) (1 \le L \lt R \le N), let X_{L, R} be the second largest
  value among P_L, P_{L+1}, \ldots, P_R.
  
  Find \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.
samples: [{"input": "3\n    2 3 1", "output": "5\n    \n\nX_{1, 2} = 2, X_{1, 3} = 2, and X_{2, 3} = 1, so the sum is 2 + 2 + 1 = 5.\n\n* * *"}, {"input": "5\n    1 2 3 4 5", "output": "30\n    \n\n* * *"}, {"input": "8\n    8 2 7 3 4 5 6 1", "output": "136"}]