CodeEff/ECCO huggingface dataset:
# Original solution
class PERM_COMB_MOD():
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def perm(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * self.finv[n-k] % self.mod % self.mod

    def comb(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.mod) % self.mod

mod = 10**9+7
P = PERM_COMB_MOD(2*10**5, mod=mod)

n = int(eval(input()))
x = list(map(int, input().split()))
base = x[-1]-x[0]
left = []
k = n-1
for i in range(k):
    a = P.perm(k, k-(i+1))*P.fac[i]
    left.append(a)
ans = base*P.fac[k]
for i in range(k):
    for j in range(1, n-1-i):
        ans += left[j]*(x[i+j+1]-x[i+j])
        ans %= mod
print(ans)


# Optimized solution
class PERM_COMB_MOD():
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def perm(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * self.finv[n-k] % self.mod % self.mod

    def comb(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.mod) % self.mod

mod = 10**9+7
P = PERM_COMB_MOD(2*10**5, mod=mod)

n = int(eval(input()))
x = list(map(int, input().split()))
base = x[-1]-x[0]
left = []
k = n-1
for i in range(k):
    a = P.perm(k, k-(i+1))*P.fac[i]
    left.append(a)
left[0] = 0
for i in range(1, k):
    left[i] += left[i-1]

ans = base*P.fac[k]
for i in range(1, n-1):
    tmp = x[i+1]-x[i]
    ans += tmp*left[i]
    ans %= mod
print(ans)
# Original solution
#----------------------------------------------------------
P = 10**9 + 7
N = 100001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b):
    if a<b or a<0 or b<0:
        return 0 # error
    return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P
#----------------------------------------------------------

n=int(eval(input()))
x=list(map(int,input().split()))
ans=0
for i in range(n-1):
    t = (x[n-1]-x[i])%P
    o =(fac[i]*fac[n-2-i])%P
    g = (comb(n-1,n-1-i)*o)%P
    t = (t * g)%P
    ans=(ans+t)%P

for i in range(n-1):
    for j in range(i+1,n-1):
        t = (x[j]-x[i])%P
        o =(fac[n-1-j+i-1]*fac[j-i-1])%P
        g = (comb(n-1,j-i+1)*o)%P
        t = (t * g)%P
        ans=(ans + t)%P
print((ans%P))


# Optimized solution
#----------------------------------------------------------
P = 10**9 + 7
N = 100001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b):
    if a<b or a<0 or b<0:
        return 0 # error
    return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P
#----------------------------------------------------------

n=int(eval(input()))
x=list(map(int,input().split()))
s = [0] * n
for i in range(n):
    s[i] = x[i] + (s[i-1] if i>0 else 0)
ans=0

for i in range(n-1):
    t = (x[n-1]-x[n-2-i])%P
    t = (t * (fac[n-1]*inv[i+1])%P)%P
    ans=(ans+t)%P
for i in range(1, n-1):
    t = (s[n-2] - s[i-1] - s[n-2-i])%P
    p = (((fac[n-1] * inv[i])%P) * inv[i+1])%P
    ans = (ans + (t*p)%P)%P

print((ans%P))
# Original solution
MOD = 10 ** 9 + 7
N = int(eval(input()))
x = list(map(int, input().split()))
x.sort()
 
kaijo = [1]
for i in range(1, N):
    kaijo.append(kaijo[-1] * i)
 
ans = 0
for i in range(N - 1):
    ans = (ans * (i + 1) + (x[-1] - x[i]) * kaijo[i]) % MOD
 
print(ans)

# Optimized solution
MOD = 10 ** 9 + 7
N = int(eval(input()))
x = list(map(int, input().split()))
x.sort()
 
kaijo = [1]
for i in range(1, N):
    kaijo.append(kaijo[-1] * i % MOD)
 
ans = 0
for i in range(N - 1):
    ans = (ans * (i + 1) + (x[-1] - x[i]) * kaijo[i]) % MOD
 
print(ans)
# Original solution
n, *x = list(map(int, open(0).read().split()))

mod = 10 ** 9 + 7

y = []
for i in range(n - 1):
    y.append(x[i + 1] - x[i])

fac = [1] * (n + 1)
for i in range(1, n):
    fac[i] = fac[i - 1] * i % mod

dp = [0] * n
ans = 0
p = 0

for i in range(n - 1):
    p = (p + pow(i + 1, mod - 2, mod))
    ans = (ans + p * y[i]) % mod

print((ans * fac[n - 1] % mod))


# Optimized solution
n, *x = list(map(int, open(0).read().split()))
mod = 10 ** 9 + 7
fac = [1] * n
for i in range(1, n):
    fac[i] = fac[i - 1] * i % mod

ans = 0
p = 0

for i in range(n - 1):
    p = (p + pow(i + 1, mod - 2, mod))
    ans = (ans + p * (x[i + 1] - x[i])) % mod

print((ans * fac[n - 1] % mod))
# Original solution
n = int(eval(input()))
x = list(map(int, input().split()))
ans = 0
p = 1
for i in range(1, n):
  p *= i
for i in range(n-1):
  ans += (x[n-1]-x[i])*p//(i+1)
ans %= 1000000007
print(ans)

# Optimized solution
n = int(eval(input()))
x = list(map(int, input().split()))
ans = 0
mod = 1000000007
p = 1
for i in range(1, n):
  p *= i
  p %= mod
for i in range(n-1):
  ans += (x[n-1]-x[i])*pow(i+1, mod-2, mod)
ans *= p
ans %= 1000000007
print(ans)
# Original solution
import sys
from fractions import Fraction
from math import factorial

rl = sys.stdin.readline


def solve():
    N = int(rl())
    x = list(map(int, rl().split()))
    MOD = 10 ** 9 + 7
    
    acc = [Fraction(0)] * N
    for i in range(1, N):
        acc[i] = acc[i - 1] + Fraction(1, i)
    
    ans = 0
    for i in range(N - 1):
        ans = ans + (x[i + 1] - x[i]) * acc[i + 1] % MOD
    
    ans = int(ans * factorial(N - 1) % MOD)
    print(ans)


if __name__ == '__main__':
    solve()


# Optimized solution
import sys
from math import factorial

rl = sys.stdin.readline


def mod_div(x, y, mod=10 ** 9 + 7):
    return x * pow(y, mod - 2, mod) % mod


def solve():
    N = int(rl())
    x = list(map(int, rl().split()))
    MOD = 10 ** 9 + 7
    
    acc = [0] * N
    k = factorial(N - 1)
    for i in range(1, N):
        acc[i] = (acc[i - 1] + k) % MOD
        k = k * mod_div(i, i + 1) % MOD
    
    ans = 0
    for i in range(N - 1):
        ans = (ans + (x[i + 1] - x[i]) * acc[i + 1]) % MOD
    print(ans)


if __name__ == '__main__':
    solve()
# Original solution
N = int(eval(input()))
Xs = [0] + list(map(int, input().split()))
mod = 10**9 + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

NNN = (10**6)
g1 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

mxx = Xs[-1]
r = 0
for i in range(N):
    i += 1
    for j in range(1, N-i):
        ue = mul(g1[N-1], Xs[i+j] - Xs[i])
        ff = mul(mul(ue, inverse[j+1]), inverse[j])
        r = (r + ff) % mod
    ue = mul(g1[N-1], Xs[N]-Xs[i])
    ff = mul(ue,inverse[N-i])
    r = (r+ff)%mod

print(r)


# Optimized solution
N = int(eval(input()))
Xs = list(map(int, input().split()))
mod = 10**9 + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
NNN = (10**6)
g1 = [1, 1]
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

mxx = Xs[-1]
r = 0
r2 = 0
for i in range(N-1):
    r = (r+mul(mul(g1[N-1],inverse[i+1]),Xs[N-1]-Xs[i]))%mod
print(r)
# Original solution
N = int(eval(input()))
Xs = list(map(int, input().split()))
mod = 10**9 + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
NNN = (10**6)
g1 = [1, 1]
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

mxx = Xs[-1]
r = 0
r2 = 0
for i in range(N-1):
    r = (r+mul(mul(g1[N-1],inverse[i+1]),Xs[N-1]-Xs[i]))%mod
print(r)


# Optimized solution
N,*X=list(map(int,open(0).read().split()))
M,g,q,r=10**9+7,1,[1,1],0
for i in range(1,N):
 r,g=(r+q[-1]*(X[-1]-X[i-1]))%M,g*i%M
 q+=[M//(-~i)*-q[M%(-~i)]%M]
print((r*g%M))
# Original solution
N,*X=list(map(int,open(0).read().split()));M,g,r,h,i=10**9+7,1,0,[1],N;exec("i-=1;h+=[h[-1]*i%M];"*N+"r,g=(r+g*h[N-2-i]*(X[-1]-X[i]))%M,g*-~i%M;i+=1;"*N);print(r)

# Optimized solution
N,*X=list(map(int,open(0).read().split()));M,g,r,h,i=10**9+7,1,0,[1],N
while i:i-=1;h+=[h[-1]*i%M]
while i<N:r,g=(r+g*h[N-2-i]*(X[-1]-X[i]))%M,g*-~i%M;i+=1
print(r)
# Original solution
n = int(eval(input()))
x = list( map(int, input().split()))


def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod

ans = 0
MOD = 10**9 + 7

factorial = 1
for i in range(2,n):
    factorial = (factorial * i%MOD) %MOD

p = [0]*(n-1)
p[0] = 1 * factorial%MOD

for i in range(1,n-1):
    p[i] = p[i-1] + factorial*mod_inv(i+1,MOD)
    p[i] %= MOD

for i in range(n-1):
    ans += (x[i+1]-x[i])%MOD*p[i]
    ans %= MOD

print((int(ans)))



# Optimized solution
n = int(eval(input()))
x = list( map(int, input().split()))
MOD = 10**9 + 7

def make_mod_inv(l,p): # lまでの逆元を作る
    mod_inv = [0, 1] + [0] * (l+3) # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる
    for i in range(2, l+5):
        mod_inv[i] = -mod_inv[p % i] * (p // i) % p
    return mod_inv

mod_inv = make_mod_inv(n-1,MOD)

ans = 0

factorial = 1
for i in range(2,n):
    factorial = (factorial * i%MOD) %MOD

p = [0]*(n-1)
p[0] = 1 * factorial%MOD

for i in range(1,n-1):
    p[i] = p[i-1] + factorial*mod_inv[i+1]
    p[i] %= MOD

for i in range(n-1):
    ans += (x[i+1]-x[i])%MOD*p[i]
    ans %= MOD

print((int(ans)))
# Original solution
def per(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r=n-r
    return g1[n] * g2[r] % mod

mod = 10**9+7 #出力の制限
N = 10**5+5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


n=int(eval(input()))
A=[1]
for i in range(1,n-1):
  A.append(A[-1]*(i+1)+per(i,i,mod))
X=list(map(int,input().split()))
Y=[X[1]-X[0]]
for i in range(2,n):
  Y.append(X[i]-X[i-1])
ans=0
for i in range(n-1):
  if n-2-i==0:
    ans=ans+A[i]*Y[i]
  else:
    ans=(ans+A[i]*per(n-1,n-2-i,mod)*Y[i])%(10**9+7)
print((ans%mod))

# Optimized solution
n=int(eval(input()))
x=list(map(int,input().split()))
a=1
B=[1,1]
mod=10**9+7
for i in range(2,n):
  a=a*i%mod
  B.append(pow(i,mod-2,mod))
d=[0]*(n-1)
for i in range(n-1):
  d[i]=x[i+1]-x[i]
D=[d[-1]]
for i in range(n-2):
  D.append(D[-1]+d[-2-i])
D=D[::-1]
ans=0
for i in range(n-1):
  ans=(ans+D[i]*a*B[i+1])%mod
print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
mod = int(1e+9 + 7)
p = mod - 2
S = []
while p != 0:
  S = [p%2] + S[:]
  p //= 2
frac = 1
for i in range(N - 1):
  frac *= i+1
  frac %= mod
T = 0
for i in range(N - 1):
  k = 1
  for j in range(len(S)):
    if S[j] == 1:
      k *= i+1
      k %= mod
    if j != len(S) - 1:
      k *= k
      k %= mod
  T += (frac * k * (A[N - 1] - A[i])) % mod
  T %= mod
print((T%mod))

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
mod = int(1e+9 + 7)
def inved(a):
  x, y, u, v, k, l = 1, 0, 0, 1, a, mod
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x

frac = 1
for i in range(N - 1):
  frac *= i+1
  frac %= mod
T = 0
for i in range(N - 1):
  k = inved(i+1)
  T += (k * (A[N - 1] - A[i])) % mod
  T %= mod
print(((T*frac)%mod))
# Original solution
import sys
import bisect
input = sys.stdin.readline

def main():
    n = int(eval(input()))
    a = [int(eval(input())) for _ in range(n)]
    
    odd = a[::2]
    even = a[1::2]
    
    odd.sort()
    even.sort()
    
    
    ans = 0
    for i, v in enumerate(odd):
        ans += bisect.bisect(even[i:], v)
    
    print(ans)
    

    
if __name__ == "__main__":
    main()


# Optimized solution
import sys
input = sys.stdin.readline


def main():
    n = int(eval(input()))
    a = [[int(eval(input())), i] for i in range(n)]
    a.sort()
    
    ans = 0
    for i in range(n):
        if i%2 != a[i][1]%2:
            ans += 1
    
    print((ans//2))


if __name__ == "__main__":
    main()
# Original solution
N = int(eval(input()))

A = [int(eval(input())) for _ in range(N)]

B = tuple(sorted(A))

ans = 0
skip_flag = False
for i in range(N):
    if skip_flag == False:
        idx = A.index(B[i])
        if abs(i - idx) % 2 == 0: # あまり０なら操作２だけで所定の位置に動かせる
            continue
        else:
            ans += 1
            # 次のやつも同時にできるか
            if i < N-1:
                next_idx = A.index(B[i+1])
                if abs(i+1 - next_idx) % 2 == 1:
                    skip_flag = True
    else:
        skip_flag = False
        continue

print(ans)


# Optimized solution
import math

N = int(eval(input()))

A = [int(eval(input())) for _ in range(N)]

idx_A = {}
for i in range(N):
    idx_A[A[i]] = i

B = tuple(sorted(A))

"""
ソート後の位置までの距離が奇数だと操作１が一回必要になる
一度の操作１で最大で２個までのソート後の位置までの距離が奇数のものを偶数にずらしてあげられる
ので、正しい位置までの距離が奇数のものの個数をしらべて、最小の操作１の回数を求める
"""
cnt = 0
for i in range(N):
    if abs(i - idx_A[B[i]]) % 2 == 0: # あまり０なら操作２だけで所定の位置に動かせる
        continue
    else:
        cnt += 1


print((math.ceil(cnt/2)))
# Original solution
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]

D = {a:i for i,a in enumerate(sorted(A))}

A = [D[A[i]] for i in range(N)]

odd = [A[i] for i in range(N) if i%2 == 0]
even = [A[i] for i in range(N) if i%2 == 1]

odd.sort()
even.sort()

B = []

for i in range(N):
    if i%2 == 0:
        B.append(odd[i//2])
    else:
        B.append(even[i//2])

count = 0

for i in range(N):
    if i%2 == 0 and B[i]%2 != 0:
        count += 1

print(count)

# Optimized solution
N = int(eval(input()))
A = [int(eval(input())) for _ in range(N)]

D = {a:i for i,a in enumerate(sorted(A))}

A = [D[A[i]] for i in range(N)]

count = 0

for i in range(N):
    if i%2 == 0 and A[i]%2 != 0:
        count += 1

print(count)
# Original solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n = int(readline())
a = [int(readline()) for i in range(n)]
k = [ai for i,ai in enumerate(a) if i%2 == 0]
g = [ai for i,ai in enumerate(a) if i%2 == 1]
k.sort()
g.sort()
ans = 0

from bisect import insort
from collections import deque

for i in range(n-1):
  K = (i+1)//2
  G = i//2
  p = k[K]; q = g[G]
  if (K == G and p > q) or (K > G and p < q):
    ans += 1
    insort(k,q)
    insort(g,p)
    k = deque(k)
    g = deque(g)
    k.popleft()
    g.popleft()
    k = list(k)
    g = list(g)
    
print(ans)

# Optimized solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n = int(readline())
a = [int(readline()) for i in range(n)]
k = [ai for i,ai in enumerate(a) if i%2 == 0]
k = set(k)
a.sort()
ans = 0
for i,ai in enumerate(a):
  if ai in k and i%2 == 1:
    ans += 1
print(ans)
# Original solution
n = int(eval(input()))
a = [int(eval(input()))for _ in range(n)]
o = a[::2]
e = a[1::2]
o.sort()
e.sort()
l = [0] * n
for i in range(n):
  if i % 2 == 0:
    l[i] = o[i // 2]
  else:
    l[i] = e[(i - 1) // 2]
ans = 0
for _ in range(n):
  for i in range(n - 1):
    if l[i] > l[i + 1]:
      ans += 1
      l[i], l[i + 1] = l[i + 1], l[i]
print(ans)

# Optimized solution
n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]
d = [{x: 0 for x in a} for _ in range(2)]
b = sorted(a)
for i in range(n):
    if i % 2:
        d[0][a[i]] += 1
        d[1][b[i]] += 1
t1 = 0
t2 = 0
for v1, v2 in zip(list(d[0].values()), list(d[1].values())):
    if v1 > v2:
        t1 += v1 - v2
print(t1)
# Original solution
#!/usr/bin/env python3
#AGC3 C

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]
b = sorted(a)
lst = []
for i in range(n):
    if a[i] != b[i]:
        r = bl(b,a[i])
        if i % 2 ^ r % 2 == 0:
            continue
        lst.append(a[i])
lst.sort()
m = len(lst)
ans = m//2
print(ans)


# Optimized solution
#!/usr/bin/env python3
#AGC3 C

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]
b = sorted(a)
lst = []
for i in range(n):
    if a[i] != b[i]:
        r = bl(b,a[i])
        if i % 2 ^ r % 2 == 0:
            continue
        lst.append(a[i])
m = len(lst)
ans = m//2
print(ans)
# Original solution
import sys
from collections import defaultdict
input = sys.stdin.readline
def main():
    N = int( eval(input()))
    A = [ int( eval(input())) for _ in range(N)]
    B = sorted(A)
    d = defaultdict( int)
    for i in range(N):
        d[B[i]] = i
    odd = 0
    for i in range(N):
        if (i+1)%2 == d[A[i]]%2 and d[A[i]]%2 == 1:
            odd += 1
    print(odd)
    
if __name__ == '__main__':
    main()

# Optimized solution
# import sys
from collections import defaultdict
# input = sys.stdin.readline
def main():
    N = int( eval(input()))
    A = [ int( eval(input())) for _ in range(N)]
    B = sorted(A)
    d = defaultdict( int)
    for i in range(N):
        d[B[i]] = i
    odd = 0
    for i in range(N):
        if (i+1)%2 == d[A[i]]%2 and d[A[i]]%2 == 1:
            odd += 1
    print(odd)
    
if __name__ == '__main__':
    main()
# Original solution
n = int(eval(input()))
nums = [int(eval(input())) for _ in range(n)]
standard = nums[:]
standard.sort()
ans = 0

for i in range(n):
    p = nums[i]
    x = standard.index(p)
    if abs(x - i) % 2 == 1:
        ans += 1

print((ans // 2))

# Optimized solution
n = int(eval(input()))
nums = [[int(eval(input())), i] for i in range(n)]
nums.sort()
ans = 0

for i in range(n):
    if abs (i - nums[i][1]) % 2 == 1:
        ans += 1

print((ans // 2))
# Original solution
from heapq import heappop, heappush
N = int(eval(input()))
idx = {}
A = []
ans = 0
for i in range(N):
  a = int(eval(input()))
  idx[a] = i%2
  heappush(A,a)

for i in range(N):
  x = heappop(A)
  if idx[x] != i%2:
    ans += 1
print((ans//2))

# Optimized solution
from heapq import heappop, heappush
N = int(eval(input()))
A = []
memo = {}
count = 0
for i in range(N):
  a = int(eval(input()))
  if i%2 == 1:
    memo[a] = 1
  else:
    memo[a] = 0
  heappush(A,a)

for i in range(N):
  x = heappop(A)
  if i%2 != memo[x]:
    count += 1
print((count//2))
# Original solution
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [[INT(), i] for i in range(N)]

A.sort(key = lambda x:x[0])

cnt = 0
for i, (x, idx) in enumerate(A):
	if i%2 != idx%2:
		cnt += 1

print((cnt//2))

# Optimized solution
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = [INT() for _ in range(N)]

zipped = {x:i+1 for i, x in enumerate(sorted(A))}
A = [zipped[x] for x in A]

print((sum(x%2==0 for x in A[::2])))
# Original solution
from bisect import bisect_left
N = int(eval(input()))
A = list(int(eval(input())) for _ in range(N))
A = [bisect_left(sorted(A),a) for a in A]
print(((sum((i-j)%2 for i,j in enumerate(A))+1)//2))

# Optimized solution
from bisect import bisect_left
N = int(eval(input()))
A = list(int(eval(input())) for _ in range(N))
S = sorted(A)
A = [bisect_left(S,a) for a in A]
print(((sum((i-j)%2 for i,j in enumerate(A))+1)//2))
# Original solution
n = int(eval(input()))
a = [int(eval(input())) for i in range(n)]

def three_change(i):
    a[i], a[i + 2] = a[i + 2], a[i]

def two_change(i):
    a[i],a[i + 1] = a[i + 1], a[i]

sorted_a = a[:]
sorted_a = sorted(sorted_a)


tar_ind = n - 1
count = 0
while (tar_ind >= 0):
    target = sorted_a[tar_ind]
    if(target != a[tar_ind]):
        cur_ind = a.index(target)
        tmp = tar_ind - cur_ind
        m2 = tmp // 2
        m1 = tmp % 2
        count += m1
        for i in range(m2):
            three_change(cur_ind)
            cur_ind += 2
        for i in range(m1):
            two_change(cur_ind)
            cur_ind += 1
    tar_ind -= 1

print(count)


# Optimized solution
n = int(eval(input()))
a = [int(eval(input())) for i in range(n)]

even_num = set([a[i] for i in range(0,n) if i % 2 == 0])

a = sorted(a)

odd_num = set([a[i] for i in range(0, n) if i % 2 == 1])

count = len(even_num & odd_num)
print(count)