Harryxun/stf_run huggingface dataset:
class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

n,k = map(int,input().split())
seg = SegTree(400000)
# a = [0]*n
# seg.build(a)
for i in range(n):
    a = int(input())
    seg.set_val(a,seg.fold(a-k,a+k+1) + 1)

print(seg.fold(0,400000))

### FIXED CODE ###



class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

n,k = map(int,input().split())
seg = SegTree(300001)
# a = [0]*n
# seg.build(a)
for i in range(n):
    a = int(input())
    seg.set_val(a,seg.fold(max(0,a-k),min(300001,a+k+1)) + 1)

print(seg.fold(0,300001))
import numpy as np
n,k = map(int,input().split())
h = list(map(int,input().split()))

dp = np.full
dp[0] = 0

for i in range(n):
    for j in range(k+1):
        if i+j<n:
            dp[i + j] = min(dp[i] + abs(h[i] - h[i + j]), dp[i + j])
print(dp[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))

dp = [1000000000 for i in range(n)]
dp[0] = 0

for i in range(n):
    for j in range(k+1):
        if i+j<n:
            dp[i + j] = min(dp[i] + abs(h[i] - h[i + j]), dp[i + j])
print(dp[n-1])
# import time
N, C = map(int, input().split())              # 同上。map関数を使うとこのように書ける

D = [[0 for i in range(C)] for j in range(C)]
c = [[0 for i in range(N)] for j in range(N)]
# iwakan = [[[0 for i in range(N)] for j in range(N)] for k in range(C)]

for i in range(C):
    D[i] = list(map(int, input().split()))

for i in range(N):
    c[i] = list(map(int, input().split()))

# まず違和感リストを作る。
# for i in range(C):
#     for j in range(N):
#         for k in range(N):
#             iwakan[i][j][k] = D[c[j][k] - 1][i]

'''
Gij0 : (i + j) % 3 == 0 となる場所
Gij1 : (i + j) % 3 == 1 となる場所
Gij2 : (i + j) % 3 == 2 となる場所
とした時に、
Gijnに属する場所全ての色をaに塗り替える場合の違和感の合計を
iwakan[n][a]とする。
iwakan[n][a]を全て求めるための計算量は、30*500*500 = 7500000
iwakan を用いて全ての色の塗り替えの組み合わせを求めるための計算量は
30 * 29 * 28 = 24360
'''

# t1 = time.time()

# Gijnに属する色の数を合計したリストを作る。
numOfColors = [[0 for i in range(C)] for j in range(3)]
for i in range(N):
    for j in range(N):
        if (i + j) % 3 == 0:
            numOfColors[0][c[i][j] - 1] = numOfColors[0][c[i][j] - 1] + 1
        if (i + j) % 3 == 1:
            numOfColors[1][c[i][j] - 1] = numOfColors[1][c[i][j] - 1] + 1
        if (i + j) % 3 == 2:
            numOfColors[2][c[i][j] - 1] = numOfColors[2][c[i][j] - 1] + 1

iwakan = [[0 for i in range(C)] for j in range(3)]
for i in range(3):
    for j in range(C):
        for a in range(C):
            iwakan[i][j] = iwakan[i][j] + numOfColors[i][a] * D[a][j]

# t2 = time.time()

sum_min = float("inf")
for i in range(C):
    for j in range(C):
        for k in range(C):
            if (i == j) or (j == k) or (k == i):
                pass
            else:
                sum_tmp = iwakan[0][i] + iwakan[1][j] + iwakan[2][k]
                if sum_min > sum_tmp:
                    sum_min = sum_tmp

# t3 = time.time()

print(sum_min)

# elapsed_time1 = t2 - t1
# elapsed_time2 = t3 - t2
# print(f'time1: {elapsed_time1}')
# print(f'time2: {elapsed_time2}')


### FIXED CODE ###

n = int(input())

if n <= 999:
    print("ABC")
else:
    print("ABD")
A,B,K = map(int(),input().rstrip().split())
 
for i in range(K):
	if i % 2 == 0:
    	B = B + A/2
    	A = A/2
	else:
   		A = A + B/2
    	B=B/2
print ('{} {}'.format(A,B))

### FIXED CODE ###

A, B, K = map(int, input().split())
for i in range(0, K):
    if(i & 1):
        if(B & 1):
            B -= 1
        A += B//2
        B //= 2
    else:
        if(A & 1):
            A -= 1
        B += A//2
        A //= 2
print("{0} {1}".format(A, B))
n=int(input())
l=list(map(int,input().split()))
x=10**9+7
if max(l)==min(l):
    print(0)
else:
        
    for i in range(min(l),max(l)+1):
        te=0
        
        for j in l:
            te=te+(abs(j-i))**2
        #print(i,te)
        x=min(x,te)
    print(x)        

### FIXED CODE ###

n=int(input())
print(int(n*(n+1)/2))
n,k=map(int,input().split())
t=n%k
n=min(t,k)
print(n)

### FIXED CODE ###

x,y,z=map(int,input().split())
print('{} {} {}'.format(z,x,y))
x, y, a, b, c = map(int, input().split())
p =list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p = sorted(p)
p = sorted(p)

p = p[(len(p)-x):]
q = q[(len(q)-y):]
r=r+p
r=r+q
r = sorted(r)
print(sum(r[(len(r)-x-y):]))


### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p =list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p = sorted(p)
q = sorted(q)

p = p[(len(p)-x):]
q = q[(len(q)-y):]
r = r + p
r = r + q
r = sorted(r)
print(sum(r[(len(r)-x-y):]))
s1,s2,s3=map(int,input().split())
if 0 == (s1+s2+s3):
  print(0)
elif 1 == (s1+s2+s3):
  print(1)
elif 2 == (s1+s2+s3):
  print(2)
else 3 == (s1+s2+s3):
  print(3)

### FIXED CODE ###

s=str(input())
print(s.count('1'))
N, Q = map(int, input().split())

T = [[] for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)

ans = [0 for i in range(N)]

for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(n, r):
    for i in T[n]:
        if i != r:
            ans[i] += ans[n]
            dfs(i, n)

dfs(0, -1)

print(*ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline

N, Q = map(int, input().split())

T = [[] for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)

ans = [0 for i in range(N)]

for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(n, r):
    for i in T[n]:
        if i != r:
            ans[i] += ans[n]
            dfs(i, n)

dfs(0, -1)

print(*ans)
i = 1
while True:
    x = int(input)
    if x == 0:
        break
    print(f"Case {i}: {x}")
    i += 1


### FIXED CODE ###

i = 1
while True:
    x = int(input())
    if x == 0:
        break
    print(f"Case {i}: {x}")
    i += 1
N = int(input())
S = []
for i in range(N):
    S.append(input())

kintama = 0
for i in range(len(S)):
    A = list(S[i])
    for j in range(i+1,len(S)+1):
        B = list(S[j])
        if set(A)==set(B):
            kintama += 1

print(kintama)



### FIXED CODE ###

#n = int(input())
#L = list(map(int, input().split()))
import math
import sys
import heapq
import fractions


def cmb(n, r):
    if n - r < r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

N = int(input())
s = []
n = 0
for i in range(N):
    s.append(list(input()))
ans = 0


for i in range(N):
    s[i].sort()
s.sort()

for i in range(1,N):

    if s[i]==s[i-1]:
        n += 1
        if i == N-1:
            ans += cmb(n+1, 2)
    else:
        if n > 0:
            ans += cmb(n+1,2)
            n = 0
print(ans)
n=int(input())
m=int(input())
print((i*i)-m)

### FIXED CODE ###

n=int(input())
m=int(input())
print((n*n)-m)
import math

A, B, C, D = map(int, input().split())

A -= 1

lcm = (C * D) // math.gcd(C, D)

excluded = A - (A // C + A // D - A // lcm)
num = B - (B // C + B // D - B // lcm)

print(num - excluded)

### FIXED CODE ###

import fractions

A, B, C, D = map(int, input().split())

A -= 1

lcm = (C * D) // fractions.gcd(C, D)

excluded = A - (A // C + A // D - A // lcm)
num = B - (B // C + B // D - B // lcm)

print(num - excluded)
def sol():
    h,w=map(int,input().split())
    c=[list(map(int,input().split())) for i in range(10)]
    a=[list(map(int,input().split())) for i in range(h)]
    for k in range(10):
        for i in range(10):
            for j in range(10):
                #if (c[i][k]!=0 and c[k][j]!=0): c[i][j]=min(c[i][j],c[i][k]+c[k][j])
                c[k][j]!=0): c[i][j]=min(c[i][j],c[i][k]+c[k][j])
    ans=0
    for i in range(h):
        for j in range(w):
            if a[i][j]==-1: pass
            else: ans+=c[a[i][j]][1]
    print(ans)

if __name__=="__main__":
    sol()

### FIXED CODE ###

h,w=map(int,input().split())
c=[]
for i in range(10):
    l=[int(i) for i in input().split()]
    c.append(l)
a=[]
for i in range(h):
    l=[int(i) for i in input().split()]
    a.append(l)
p=[0]*10
for i in range(10):
    if i==1: continue
    d=[1003]*10
    d[i]=0
    q=set([i])
    while 1:
        if len(q)==0: break
        x=q.pop()
        for j in range(10):
            if i==j: continue
            if (d[j]>d[x]+c[x][j]):
                d[j]=d[x]+c[x][j]
                q.add(j)
    p[i]=d[1]
ans=0
for i in range(h):
    for j in range(w):
        if a[i][j]==-1: pass
        else: ans+=p[a[i][j]]
print(ans)
from sys import stdin
N,P=[int(x) for x in stdin.readline().rstrip().split()]
for i in reversed(range(int(pow(P,(1/N))))):
    tmp=i**N
    if P==1:
        ans=1
        break
    if N==1:
        ans=P
        break
    if P%tmp==0:
        ans=i
        break
print(ans)

### FIXED CODE ###

import math
from sys import stdin
N,P=[int(x) for x in stdin.readline().rstrip().split()]
for i in reversed(range(round(math.pow(P,(1/N)))+1)):
    tmp=math.pow(i,N)
    if P==1:
        ans=1
        break
    if N==1:
        ans=P
        break
    if P%tmp==0:
        ans=i
        break
print(ans)
n, q = map(int, input().split())
c = []
r = [(n - 1, -1)]
t = 0
for i in range(q):
    k, x = map(int, input().split())
    if k == 1:
        c.append((x - 1, t))
    else:
        r.append((x - 1, t))
        t += 1
c.sort()
r.sort()
idx = 0
ans = (len(c)) * (r[0][0])
for i in range(len(r) - 1):
    x, t = r[i]
    tmp = idx
    while idx < len(c) and c[idx][1] > t:
        idx += 1
    ans += c[idx][0]
    ans += (len(c) - idx) * (r[i + 1][0] - x)
print((n - 2) * (n - 2) - ans + len(c) + len(r) - 1)


### FIXED CODE ###

n, q = map(int, input().split())
c = [(n - 1, -1)]
r = [(n - 1, -1)]
t = 0
for i in range(q):
    k, x = map(int, input().split())
    if k == 1:
        c.append((x - 1, t))
    else:
        r.append((x - 1, t))
        t += 1
c.sort()
r.sort()
idx = 0
ans = (len(c) - 1) * (r[0][0])
for i in range(len(r) - 1):
    x, t = r[i]
    tmp = idx
    while idx < len(c) and c[idx][1] > t:
        idx += 1
    ans += c[idx][0]
    ans += (len(c) - idx - 1) * (r[i + 1][0] - x)
print((n - 2) * (n - 2) - ans + len(c) + len(r) - 2)
a,b=[int(x) for x in input().split()]
if (a%3==1 and b%d==1) or (a%3==2 and b%3==2):
  print('Possible')
else:
  print('Impposible')

### FIXED CODE ###

a,b=[int(x) for x in input().split()]
if (a%3==1 and b%3==1) or (a%3==2 and b%3==2):
  print('Impossible')
else:
  print('Possible')
g = {}
n=int(input())
m = [-1]*n

def dfs(graph,node,height):
    global m
    global zeros
    global ones
    m[node-1]=height
    if height==0:
      zeros+=1
    if height==1:
      ones+=1
    for n in graph[node]:
      if m[n-1]==-1:
        dfs(graph,n,1-height)

zeros=0
ones=0
for i in range(n-1):
  a,b=map(int,input().split())
  if not a in g:
    g[a]=[b]
  else:
    g[a].append(b)
  if not b in g:
    g[b]=[a]
  else:
    g[b].append(a)
dfs(g,1,0)
ans=[0]*n
used=[0]*n
r=n//3
if 3*(r+1)<=n:
  r+=1
if zeros<=r:
  current=3
  for i in range(n):
    if m[i]==0:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==1:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
elif ones<=r:
  current=3
  for i in range(n):
    if m[i]==1:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==0:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
else:
  print(a)

### FIXED CODE ###

g = {}
n=int(input())
m = [-1]*n
import sys
sys.setrecursionlimit(1000000000)
def dfs(graph,node,height):
    global m
    global zeros
    global ones
    m[node-1]=height
    if height==0:
      zeros+=1
    if height==1:
      ones+=1
    for n in graph[node]:
      if m[n-1]==-1:
        dfs(graph,n,1-height)

zeros=0
ones=0
for i in range(n-1):
  a,b=map(int,input().split())
  if not a in g:
    g[a]=[b]
  else:
    g[a].append(b)
  if not b in g:
    g[b]=[a]
  else:
    g[b].append(a)
dfs(g,1,0)
ans=[0]*n
used=[0]*n
r=n//3
if 3*(r+1)<=n:
  r+=1
if zeros<=r:
  current=3
  for i in range(n):
    if m[i]==0:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==1:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
elif ones<=r:
  current=3
  for i in range(n):
    if m[i]==1:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==0:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
else:
  if zeros<ones:
    current=1
    for i in range(n):
      if m[i]==0:
        ans[i]=current
        used[current-1]=1
        current+=3
        if current>n:
          current=3
    counter=0
    for i in range(n):
      if m[i]==1:
        while True:
          if used[counter]==0:
            ans[i]=counter+1
            counter+=1
            break
          counter+=1
  else:
    current=1
    for i in range(n):
      if m[i]==1:
        ans[i]=current
        used[current-1]=1
        current+=3
        if current>n:
          current=3
      counter=0
    for i in range(n):
      if m[i]==0:
        while True:
          if used[counter]==0:
            ans[i]=counter+1
            counter+=1
            break
          counter+=1
for i in ans:
  print(i)
H,W = map(int,input().split())
if H%2 != 0:
  H= H+1
if W%2 != 0:
  W=W+1
print(int(H*W/2))

### FIXED CODE ###

l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
n = int(input())
print(l[n-1])
if __name__ == "__main__":
    num = int(input())
    base_list=[]
    tmp_list=[]
    ans=0
    base_list = input().split()
    tmp_list = deepcopy(base_list)
    for i in base_list:
        print("i:"+i)
        tmp_list.remove(i)
        for j in tmp_list:
            ans+=int(i)*int(j)
    print(ans)

### FIXED CODE ###

from copy import deepcopy

if __name__ == "__main__":
    num = int(input())
    base_list=[]
    tmp_list=[]
    ans=0
    base_list = input().split()
    tmp_list = deepcopy(base_list)
    for i in base_list:
        tmp_list.remove(i)
        for j in tmp_list:
            ans+=int(i)*int(j)
    print(ans)
N = int(input())
A = list(map(int, input().split()))

cnt1 = 0
for i in range(8):
  v1 = i * 400
  v2 = (i + 1) * 400 - 1
  for j in range(N):
    if v1 <= A[i] <= v2:
      cnt1 += 1
      break

cnt2 = 0
for i in range(N):
  if A[i] >= 3200:
    cnt2 += 1

print(cnt1, cnt2)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

cnt1 = 0
for i in range(8):
  v1 = i * 400
  v2 = (i + 1) * 400 - 1
  for j in range(N):
    if v1 <= A[j] and A[j] <= v2:
      cnt1 += 1
      break

cnt2 = 0
for i in range(N):
  if A[i] >= 3200:
    cnt2 += 1

if cnt1 == 0:
  print(1, cnt2)
else:
  print(cnt1, cnt1 + cnt2)
def main():
    N, M = map(int, input().split())
    AB = [[] for _ in range(N)]

    for _ in range(M):
        a,b = map(lambda x: int(x)-1, input().split())
        AB[a].append(b)
        AB[b].append(a)

    def dfs(v):
        visited[v] = 1
        for i in AB[v]:
            if visited[i]:
                continue
            dfs(i)

    visited = [0]*N
    cnt = 0
    for i in range(N):
        if visited[i]:
            continue
        dfs(i)
        cnt += 1
    print(cnt-1)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())

AB = [[] for _ in range(N)]

for _ in range(M):
    a,b = map(lambda x: int(x)-1, input().split())
    AB[a].append(b)
    AB[b].append(a)

visited = [0] * N
ans = []
for i in range(N):
    if visited[i]:
        continue
    group = [i]
    d = deque(AB[i])
    while d:
        s = d.popleft()
        if visited[s]:
            continue
        visited[s] = 1
        group.append(s)
        for k in AB[s]:
            d.append(k)
    ans.append(len(group))

print(len(ans)-1)
a,b = (int,input().split())
print(a*b, (a+b)*2)


### FIXED CODE ###

a,b = map(int,input().split())

print(a*b,(a+b)*2)
N=int(input())
x=[list(map(int,input().split())) for _ in range(N)]
Cx=0
Cy=0
H=0
dp=[[0]*101 for i in range(101)]
ans=10**10
for i in range(N):
  for j in range(101):
    for k in range(101):
      count=abs(x[i][0]-j)+abs(x[i][1]-k)+x[i][2]
      if dp[j][k]!=i*count:
        dp[j][k]=0
      else:
        dp[j][k]+=count
      ans=min(ans,x[i][2])
p=10**19
a=0
b=0
for i in range(101):
  for j in range(101):
    if dp[i][j]%N==0 dp[i][j]!=0:
      if p!=min(p,dp[i][j]//N):
        a=i
        b=j
        p=min(p,dp[i][j]//N)
print(a,b,p)

### FIXED CODE ###

N=int(input())
x=[list(map(int,input().split())) for _ in range(N)]
x.sort(key=lambda x:-x[2])
dp=[[0]*101 for i in range(101)]
bp=[[0]*101 for i in range(101)]
for j in range(101):
  for k in range(101):
    a,b,c=x[0]
    r=0
    asa=abs(a-j)+abs(b-k)+c
    for i in range(N):
      count=abs(x[i][0]-j)+abs(x[i][1]-k)
      if x[i][2]==max(asa-count,0):
        r+=1
    if r==N:
      print(j,k,asa)
      exit()
s = input()
ans = 0
while b:
  b = 0
  c = s.count("BW")
  if c:
    ans += c
    b = 1
    s = s.replace("BW", "WB")
print(ans)


### FIXED CODE ###

s = input()
t = 0
c = 0
for i in range(len(s)):
  if s[i] == "W":
    t += i
    c += 1
print(t-c*(c-1)//2)
a,b,c,d,e = map(int,input().split())

print(c*60+d-(a*60+b)-e)


### FIXED CODE ###

S = input()
print(S.replace("?","D"))
a, b, c = [int(i) for i in input().split()]
nums = 0
for i in range(a,c+1)
    if i%b ==0 or b%i==0 :
        nums = nums + 1
    else:
        pass
   
print(nums)

### FIXED CODE ###

a, b, c = [int(i) for i in input().split()]
nums = 0
for i in range(a, b + 1):
    if c%i == 0:
        nums = nums + 1
    else:
        pass
print(nums)
n = raw_input()
a = map(int, raw_input().split())
   
for i in range(0, n):
   print a[n-i-1],

### FIXED CODE ###

n = input()
a = map(int, raw_input().split())
    
for i in range(0, n):
   print a[n-i-1],
#x a bを設定する
x,a,b = map(int,input().split())
#x からaまでの距離とxからbまでの距離を計算する
a_distant = (a - x)^2
b_distant = (b - x)^2
#aまでとbまでを比較して短い方を出力する
if a_distant > b_distant:
    print("B")
if b_distant > a_distant
    print("A")


### FIXED CODE ###

import math
#x a bを設定する
x,a,b = map(int,input().split())
#x からaまでの距離とxからbまでの距離を計算する

a_distant = a - x
b_distant = b - x
if a_distant < 0:
    a_distant = a_distant*(-1)
if b_distant < 0:
    b_distant = b_distant*(-1)
#aまでとbまでを比較して短い方を出力する
if a_distant > b_distant:
    print("B")
else:
    print("A")
N, K  = map(int, input().split())
M = 10 ** 9 + 7

C = [[0 for j in range(N+1)] for i in range(N+1)]
C[1][1] = 1

for i in range(2, N):
    for j in range(1, i+2):
        C[i][j] = C[i-1][j] + C[i-1][j-1]

for i in range(1, K+1):
    print(C[N-K+2][i+1] * C[K][i] %  M)

### FIXED CODE ###

N, K  = map(int, input().split())
M = 10 ** 9 + 7

C = [[0 for j in range(N+3)] for i in range(N+3)]
C[1][1] = 1

for i in range(2, N+2):
    for j in range(1, i+2):
        C[i][j] = C[i-1][j] + C[i-1][j-1]

for i in range(1, K+1):
    print(C[N-K+2][i+1] * C[K][i] %  M)
INF = float("inf")
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

X = n()

dp = [0] * (X+1)
dp[1] = 1
for i in range(2, X+1):
    if dp[i - dp[i-1]] < dp[i-1]:
        dp[i] = dp[i-1]
    else:
        dp[i] = dp[i-1]+1

print(dp[X])


### FIXED CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

X = n()

for x in range(1, X):
    if x * (x + 1) // 2 >= X:
        print(x)
        import sys
        sys.exit()

print(X)
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    A[i] = A[i] - i - 1
A = sorted(A)
medN = N//2
x = 0
for i in range(N):
    x = x + abs(A[i] - A[medN])
print(x)

### FIXED CODE ###

N = int(input())
z = N
if N % 2 != 0:
    z = 2 * N
print(z)
#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-9;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  long long ans = 1;
  vector<long long> a(n);
  bool ok = false;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] == 0) ok = true;
  }
  if (ok) {
    cout << "0\n";
    return 0;
  }
  double foo = (double)1e18;
  for (int i = 0; i < n; i++) {
    if (a[i] == 0) {
      cout << "0\n";
      return 0;
    }
    double bar = foo / a[i];
    if (bar < 1.0 * ans) {
      cout << "-1\n";
      return 0;
    }
    ans *= a[i];
  }
  cout << ans << '\n';
  return 0;
}

### FIXED CODE ###

from math import *
n = int(input())
a = [int(x) for x in input().split()]
ans = 1
ok = False
fail = False
for x in a:
  if (x == 0):
    ok = True
    break
for x in a:
  if (ans * x > 1000000000000000000):
    fail = True
    break
  ans *= x
if (ok):
  print(0)
else:
  if (fail):
    print("-1")
  else:
    print(ans)
# coding: utf-8

def main():
    N = int(input())
    d = sorted(list(map(int, input().split())))
    ans = 0
    if d[N / 2] != d[N / 2 - 1]:
        ans = d[N / 2] - d[N / 2 - 1]

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding: utf-8

def main():
    N = int(input())
    d = sorted(list(map(int, input().split())))
    ans = 0
    if d[N // 2] != d[N // 2 - 1]:
        ans = d[N // 2] - d[N // 2 - 1]

    print(ans)


if __name__ == "__main__":
    main()