output_description: Print the minimum number of times Operation 1 that Snuke has to perform.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N
      A_1
      :
      A_N
attempt: import itertools
  
  N = int(input())
  A = list(enumerate([int(input()) for _ in range(N)]))
  B = [
      iv[0] + 1
      for iv in sorted(
          enumerate([i for i, v in sorted(A, key=lambda xs: xs[1])]), key=lambda xs: xs[1]
      )
  ]
  C = list(
      itertools.chain.from_iterable(
          itertools.zip_longest(sorted(B[::2]), sorted(B[1::2]))
      )
  )
  if C[-1] == None:
      C = C[:-1]
  
  
  class SegmentTree:
      """
      Parameters
      ----------
      array : list
          to construct segment tree from
      f : func
          binary operation of the monoid
      e :
          identity element of the monoid
      size : int
          limit for array size
      """
  
      def __init__(self, array, f, e, size):
          self.f = f
          self.e = e
          self.size = size
          self.n = n = len(array)
          self.dat = [e] * n + array + [e] * (2 * size - 2 * n)
          self.build()
  
      def build(self):
          dat, n, f = self.dat, self.n, self.f
          for i in range(n - 1, 0, -1):
              dat[i] = f(dat[i << 1], dat[i << 1 | 1])
  
      def modify(self, p, v):
          """
          set value at position p (0-indexed)
          """
          f, n, dat = self.f, self.n, self.dat
          p += n
          dat[p] = v
          while p > 1:
              dat[p >> 1] = f(dat[p], dat[p ^ 1])
              p >>= 1
  
      def query(self, l, r):
          """
          result on interval [l, r) (0-indexed)
          """
          f, e, n, dat = self.f, self.e, self.n, self.dat
          res = e
          l += n
          r += n
          while l < r:
              if l & 1:
                  res = f(res, dat[l])
                  l += 1
              if r & 1:
                  r -= 1
                  res = f(res, dat[r])
              l >>= 1
              r >>= 1
          return res
  
  
  e = 0
  size = N + 1
  ST = SegmentTree([0] * N, f=lambda x, y: x + y, e=e, size=size)
  ans = N * (N + 1) // 2
  for c in C:
      ST.modify(c, ST.query(c, c + 1) + 1)
      ans -= ST.query(1, c + 1)
  print(ans)
  
problem_description: Statement
  
  Snuke got an integer sequence of length N from his mother, as a birthday
  present. The i-th (1 ≦ i ≦ N) element of the sequence is a_i. The elements are
  pairwise distinct. He is sorting this sequence in increasing order. With
  supernatural power, he can perform the following two operations on the
  sequence in any order:
  
    * Operation 1: choose 2 consecutive elements, then reverse the order of those elements.
    * Operation 2: choose 3 consecutive elements, then reverse the order of those elements.
  
  Snuke likes Operation 2, but not Operation 1. Find the minimum number of
  Operation 1 that he has to perform in order to sort the sequence in increasing
  order.
samples: [{"input": "4\n    2\n    4\n    3\n    1", "output": "1\n    \n\nThe given sequence can be sorted as follows:\n\n  * First, reverse the order of the last three elements. The sequence is now: 2,1,3,4.\n  * Then, reverse the order of the first two elements. The sequence is now: 1,2,3,4.\n\nIn this sequence of operations, Operation 1 is performed once. It is not\npossible to sort the sequence with less number of Operation 1, thus the answer\nis 1.\n\n* * *"}, {"input": "5\n    10\n    8\n    5\n    3\n    2", "output": "0"}]