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 sys
  
  input = lambda: sys.stdin.readline().rstrip()
  sys.setrecursionlimit(max(1000, 10**9))
  write = lambda x: sys.stdout.write(x + "\n")
  
  n = int(input())
  a = [None] * n
  for i in range(n):
      a[i] = int(input())
  
  from bisect import bisect_left
  
  
  def press(l):
      # xs[inds[i]]==l[i]となる
      xs = sorted(set(l))
      inds = [None] * len(l)
      for i, item in enumerate(l):
          inds[i] = bisect_left(xs, item)
      return xs, inds
  
  
  xs, inds = press(a)
  
  odd = [num for i, num in enumerate(inds) if i % 2]
  even = [num for i, num in enumerate(inds) if i % 2 == 0]
  
  odd.sort()
  even.sort()
  
  aa = [None] * n
  for i in range(n // 2 + n % 2):
      aa[2 * i] = even[i]
  for i in range(n // 2):
      aa[2 * i + 1] = odd[i]
  
  
  def init(bit, values):
      for i, v in enumerate(values):
          update(bit, i, v)
  
  
  # a1 ~ aiまでの和 O(logn)
  def query(bit, i):
      res = 0
      while i > 0:
          res += bit[i]
          i -= i & (-i)
      return res
  
  
  # ai += x(logN)
  def update(bit, i, x):
      while i <= len(bit) - 1:
          bit[i] += x
          i += i & (-i)
      return
  
  
  # 1-indexedなので注意
  bit = [0] * (n + 1)
  ans = 0
  for i, ind in enumerate(aa):
      ans += i - query(bit, ind + 1)
      update(bit, ind + 1, 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"}]