Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

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

for i in range(k):
    h.pop(h.index(max(h)))
    if len(h) == 0:
        break
print(sum(h))

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
h.sort()
if len(h) > k:
    print(sum(h[:n - k]))
else:
    print(0)
### BUGGY CODE ###


import heapq
n = int(input())
stw = []
x_list = []
y_list = []
for i in range(n):
  x, y = map(int, input().split())
  x_list += [[x, i]]
  y_list += [[y, i]]
x_list.sort()
y_list.sort()
for [u, fr], [v, to] in zip(x_list, x_list[1:]):
  stw += [[abs(u-v), fr, to]]
for [u, fr], [v, to] in zip(y_list, y_list[1:]):
  stw += [[abs(u-v), fr, to]]
  
heapq.heapify(stw)

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())


def kruskal():
  # stw = [[s0, t0, w0], [s1, t1, w1], ..., [sn, tn, wn]]
  # stw: s: 始点, t: 終点, w: st間の重み
  # stwはwを小さい順にソートされたものとする
  res = 0
  uf = UnionFind(n)
  while stw:
    w, s, t = heapq.heappop(stw)
    if not uf.isSameGroup(s, t):
      uf.Unite(s, t)
      res += w
  return res

print(kruskal())

### FIXED CODE ###

import itertools
import heapq
from heapq import heappush, heappop
global G, inp_x, inp_y

def input_graph(N):
  global G, inp_x, inp_y
  inp_x = []
  inp_y = []
  for i in range(N):
    x, y = map(int, input().split())
    inp_x.append((x, i))
    inp_y.append((y, i))
  inp_x.sort()
  inp_y.sort()
  for i in range(N-1):
    xa = inp_x[i][1]
    xb = inp_x[i+1][1]
    ya = inp_y[i][1]
    yb = inp_y[i+1][1]
    cost_x = abs(inp_x[i][0]-inp_x[i+1][0])
    cost_y = abs(inp_y[i][0]-inp_y[i+1][0])
    G[xa] += [(cost_x, xb)]
    G[xb] += [(cost_x, xa)]
    G[ya] += [(cost_y, yb)]
    G[yb] += [(cost_y, ya)]

  
def prim(V):
  global G, used
  edgelist = []
  for e in G[0]:
    heappush(edgelist, e)
  used[0] = True
  res = 0
  while edgelist:
    minedge = heappop(edgelist)
    if used[minedge[1]]:
      continue 
    v = minedge[1]
    used[v] = True 
    for e in G[v]:
      if not used[e[1]]:
        heappush(edgelist, e)
    res += minedge[0]
  return res

def main():
  global G, used
  N = int(input())
  G = [[] for _ in range(N)]
  used = [False for _ in range(N)]
  input_graph(N)
  print(prim(N))

if __name__ == "__main__":
  main()
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split(" ")))
c=0
for i in range(n):
  if l[i]>n-1-i:
    continue
  for j in range(i+1,n):
    if l[i]+l[j]==j-i:
      c+=1
      
print(c)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

N = int(input())

A = list(map(int, input().split()))
Ap = [i - A[i] for i in range(N)]
Ap.sort()

ans = 0
for i in range(N):
	ans += bisect_right(Ap, i + A[i]) - bisect_left(Ap, i + A[i])

print(ans)
### BUGGY CODE ###

#AGC047-A Integer Product
"""
小数または整数が与えられるので、その積が整数となるペアの個数を求めよ。

まず入力に10**9をかけることで、
問題を「その積が10**18の倍数となるペアの個数を求めよ」
とする。
その場合、とりあえず10**18を素因数分解すると2**18と5**18なので、
片方が因数分解済みであるとした時に、
dp[i][j] : 2**iかつ5**jの個数
として、もう片方を2**aかつ5**bであると考えた時に、
2**(i+a)>=18かつ5**(j+b)>=18となるならば、それは条件を満たす
と考えられる。

よってこの個数を数えることで問題が解けた。
"""
import sys
from decimal import Decimal
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1  = [] 
for i in range(n):
    lst1.append(int(Decimal(input())*(10**9)))

dp = [[0]*20 for _ in range(50)]

ans = 0

for i in range(n):
    res = lst1[i]
    t,f = 0,0
    while True:
        if res%2==0:
            res //= 2
            t += 1
        else:
            break
    while True:
        if res%5==0:
            res //= 5
            f += 1
        else:
            break
    #i+t>=18かつj+f>=18であるような場所からカウント
    for i in range(18-t,50):
        for j in range(18-f,20):
            ans += dp[i][j]
    dp[t][f] += 1

print(ans)


### FIXED CODE ###

#AGC047-A Integer Product
"""
小数または整数が与えられるので、その積が整数となるペアの個数を求めよ。

まず入力に10**9をかけることで、
問題を「その積が10**18の倍数となるペアの個数を求めよ」
とする。
その場合、とりあえず10**18を素因数分解すると2**18と5**18なので、
片方が因数分解済みであるとした時に、
dp[i][j] : 2**iかつ5**jの個数
として、もう片方を2**aかつ5**bであると考えた時に、
2**(i+a)>=18かつ5**(j+b)>=18となるならば、それは条件を満たす
と考えられる。

よってこの個数を数えることで問題が解けた。
"""
import sys
from decimal import Decimal
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1  = [] 
for i in range(n):
    s = readline().rstrip().decode('utf-8')
    lst1.append(int(Decimal(s)*(10**9)))

dp = [[0]*20 for _ in range(45)]

ans = 0

for i in range(n):
    res = lst1[i]
    t,f = 0,0
    while True:
        if res%2==0:
            res //= 2
            t += 1
        else:
            break
    while True:
        if res%5==0:
            res //= 5
            f += 1
        else:
            break
    #i+t>=18かつj+f>=18であるような場所からカウント
    for i in range(18-t,45):
        for j in range(18-f,20):
            ans += dp[i][j]
    dp[t][f] += 1

print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
P = [i-1 for i in P]
ans = -1e18
for si in range(N):
    x = si
    s = []
    tot = 0
    while True:
        x = P[x]
        s.append(C[x])
        tot += C[x]
        if x == si :
            break
    l = len(s)
    t = 0
    for i in range(l):
        t += s[i]
        if i+1 > K:
            break
        now = t
        if tot > 0:
            e = (K-i-1)//l
            now += tot*e
        if ans < now:
            ans = now
        else:
            ans = ans
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
P = [int(t) - 1 for t in input().split()]
C = list(map(int,input().split()))

ans = -1e18
for si in range(N):
    x = si
    s = []
    tot = 0
    while True:
        x = P[x]
        s.append(C[x])
        tot += C[x]
        if x == si:
            break
    l = len(s)
    t = 0
    for i in range(l):
        t += s[i]
        if i+1 > K:
            break
        now = t
        if tot > 0:
            e = (K-(i+1))//l
            now += tot*e
        if ans < now:
            ans = now
print(ans)
### BUGGY CODE ###

x=input()

for _ in range(10**5):
    x=x.replace('ST','')

print(len(x))

### FIXED CODE ###

x=input()
n=len(x)

t=0
cnt=0
for i in range(n-1,-1,-1):
    if x[i]=='T':
        t+=1
    elif t>0 and x[i]=='S':
        cnt+=1
        t-=1

print(n-2*cnt)
### BUGGY CODE ###

import scipy.linalg as linalg
import numpy as np

n = int(input())
coef = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    if i == n-1:
        coef[i][0] = 1/2
        coef[i][-1] = 1/2
    else:
        coef[i][i] = 1/2
        coef[i][i+1] = 1/2
    
A = np.zeros((n, n))
for i in range(n):
    A[i] = coef[i]

b = np.array([int(x) for x in input().split()])

LU = linalg.lu_factor(A)
ans = linalg.lu_solve(LU, b)

print(" ".join(map(str, map(int, ans))))

### FIXED CODE ###

n = int(input())
A = [int(x) for x in input().split()]
S = sum(A)

X_1 = S
i = 0
while 2*i+1 < n:
    X_1 -= 2 * A[2*i+1]
    i += 1

X = [0] * n
X[0] = X_1

for i in range(n-1):
    X_i_1 = 2 * A[i] - X[i]
    X[i+1] = X_i_1
    
print(" ".join(map(str, X)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict


MAX_INT = 2**62-1
sys.setrecursionlimit(10**6)

input = sys.stdin.readline

n = int(input())
g = [[] for _ in range(n+1)]

for _ in range(n-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

MOD = 10**9 + 7

fact = [1] * (n+1)
fact_inv = [0] * (n+1)

for i in range(1, n + 1):
    fact[i] = fact[i-1] * i % MOD
    fact_inv[i] = pow(fact[i], MOD-2, MOD)


def dfs(pre, cur):
    if pre in memo and cur in memo[pre]:
        return memo[pre][cur]

    num, ways = 1, 1

    for nxt in g[cur]:
        if nxt == pre:
            continue
        n, w = dfs(cur, nxt)
        num += n
        ways = ways * w % m * fi[n] % m

    ways = ways * f[num-1] % m
    memo[pre, cur] = num, ways
    return num, ways


m = MOD
memo = defaultdict(dict)
f, fi = fact, fact_inv

for i in range(1, len(g)):
    print(dfs(None, i)[1])


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from functools import reduce

MAX_INT = 2**62-1
sys.setrecursionlimit(10**7)

input = sys.stdin.readline

# @profile
MOD = 10**9 + 7


def mul_mod(*args, mod=MOD):
    return reduce(lambda a, b: a * b % mod, args)


def solve(g, f, fi, m):
    mul = mul_mod

    stack = [(0, 1)]
    pre_order = []
    n = len(g) - 1

    while stack:
        pre, cur = stack.pop()
        pre_order.append((pre, cur))

        for nxt in g[cur]:
            if nxt == pre:
                continue
            stack.append((cur, nxt))

    size = [1] * (n+1)
    dp = [1] * (n+1)

    for pre, cur in reversed(pre_order):
        dp[cur] = mul(dp[cur], f[size[cur]-1])
        dp[pre] = mul(dp[pre], dp[cur], fi[size[cur]])
        size[pre] += size[cur]

    ans = [1] * (n+1)
    ans[1] = dp[1]

    for pre, cur in pre_order[1:]:
        i = size[cur]
        temp = mul(ans[pre], f[n-i-1], fi[n-1], f[i], pow(dp[cur], m-2, m))
        ans[cur] = mul(f[n-1], temp, fi[n-i], dp[cur], fi[i-1])
    print(*ans[1:], sep='\n')


# @profile
def main():
    mul = mul_mod
    mod = MOD
    n = int(input())
    g = [[] for _ in range(n+1)]

    fact = [1] * (n+1)
    fact_inv = [0] * (n+1)

    for i in range(1, n+1):
        fact[i] = mul(fact[i-1], i)

    fact_inv[-1] = pow(fact[-1], mod-2, mod)

    for i in range(n)[::-1]:
        fact_inv[i] = mul(fact_inv[i+1], (i+1))

    for _ in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)

    solve(g, fact, fact_inv, mod)


if __name__ == "__main__":

    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

que = deque()
# 右左上下  
directions = [(0,1),(0,-1),(1,0),(-1,0)]
# 四方に一回り大きいグリッドを作る
grid = list2d(H+2, W+2, '*')
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]
        if grid[i][j] == '#':
            que.append((i, j, 0))

# 移動距離メモ
memo=[[-1]*(W+2) for i in range(H+2)]
while len(que):
    cur=que.popleft()
    if memo[cur[0]][cur[1]]!=-1:
        continue
    memo[cur[0]][cur[1]]=cur[2]
    # 4方向見る
    for direction in directions:
        x,y=map(lambda x,y: x+y, cur, direction)
        # 壁と黒はスキップ
        if grid[x][y]=='*' or grid[x][y]=='#':
            continue
        # 白を埋める
        if grid[x][y]=='.':
            grid[x][y]='#'
            que.append((x, y, cur[2]+1))
ans=0
for i in range(1, H+1):
    for j in range(1, W+1):
        ans=max(ans, memo[i][j])
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

que = deque()
# 右左上下  
directions = [(0,1),(0,-1),(1,0),(-1,0)]
# 四方に一回り大きいグリッドを作る
grid = list2d(H+2, W+2, '*')
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]
        if grid[i][j] == '#':
            que.append((i, j, 0))

# 移動距離メモ
memo=[[-1]*(W+2) for i in range(H+2)]
while len(que):
    cur=que.popleft()
    if memo[cur[0]][cur[1]]!=-1:
        continue
    memo[cur[0]][cur[1]]=cur[2]
    # 4方向見る
    for direction in directions:
        x=cur[0]+direction[0]
        y=cur[1]+direction[1]
        # 壁と黒はスキップ
        if grid[x][y]=='*' or grid[x][y]=='#':
            continue
        # 白を埋める
        if grid[x][y]=='.':
            grid[x][y]='#'
            que.append((x, y, cur[2]+1))
ans=0
for i in range(1, H+1):
        ans=max(ans, max(memo[i]))
print(ans)
### BUGGY CODE ###

import numpy as np
def knapsack(n,c):
  if dp[n][c]!=-1:
    return dp[n][c]
  
  if n < 0 :
    return 0
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n])
    opt2 = knapsack(n-1,c)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

n,c = map(int,input().split())
w =[];v=[]
size = n+1
dp = np.full((size,c+1),int(-1))
#print(dp)
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n-1,c)
print(int(result))       
        
        

### FIXED CODE ###

n,W = map(int,input().split())
wt =[];val=[]

dp = [[0 for i in range(W+1)] for j in range(n)]
for _ in range(n):
  wi , vi= map(int,input().split())
  wt.append(wi)
  val.append(vi)

for i in range(W+1):
  if i>=wt[0]:
    dp[0][i]=val[0]   
  else:
    dp[0][i]=0
    
    
    
#print(dp)  
for i in range(1,n):
  wi = wt[i]
  vi = val[i]
  for w in range(1,W+1):
    if wi <= w:
      dp[i][w] = max(vi + dp[i-1][w-wi] , dp[i-1][w] )
    else:
      dp[i][w] = dp[i-1][w]

print(dp[n-1][W])
### BUGGY CODE ###

import bisect
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
A = sorted(IL())
B = sorted(IL())
C = sorted(IL())

dp = [0]*N 

ans = 0
for i in range(N):
	dp[i] = bisect.bisect_left(A,B[i])
for i in range(N):
	ans += sum(dp[:bisect.bisect_left(B,C[i])])

print(ans)

### FIXED CODE ###

import bisect
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

# 二分探索 #
def nibutan(list,n):
	left = -1
	right = len(list)
	while left+1 != right:
		middle = (left+right)//2
		if list[middle] < n:
			left = middle
		else:
			right = middle
	return left+1

N = I()
A = sorted(IL())
B = sorted(IL())
C = sorted(IL())

dp = [0]*(N+1)

for i in range(N):
	dp[i] = nibutan(A,B[i])

num = 0
for i in range(N):
	num += dp[i]
	dp[i] = num

ans = 0
for i in range(N):
	ans += dp[nibutan(B,C[i])-1]

print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
a = [int(input()) for i in range(N)]

a = np.array(a)
max_a = np.max(a)
max_idx = np.where(a == max_a)[0]
if len(max_idx) > 1:
    for i in range(N):
        print(max_a)
else:
    premax_a = np.max(np.hstack((a[0:max_idx[0]], a[max_idx[0]+1:])))
    for i in range(N):
        if i == max_idx:
            print(premax_a)
        else:
            print(max_a)

### FIXED CODE ###

import numpy as np
N = int(input())
a = [int(input()) for i in range(N)]

# a = np.array(a)
max_a = np.max(a)
premax_a = np.sort(a)[::-1][1]

for i in range(N):
    if a[i] == max_a:
        print(premax_a)
    else:
        print(max_a)
### BUGGY CODE ###

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

nums = {}
for a in A:
    nums[a] = nums[a] + 1 if a in nums else 1
for k in A:
    res = 0
    for key in nums.keys():
        cnt = nums.get(key) - 1 if key == k else nums.get(key)
        res += cnt*(cnt-1)//2
    print(res)

### FIXED CODE ###

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

nums = {}
for a in A:
    nums[a] = nums[a] + 1 if a in nums else 1
res = 0
for key in nums.keys():
    res += nums[key]*(nums[key]-1)//2
for a in A:
    print( res-nums[a]+1 )
### BUGGY CODE ###

N=int(input())
S=[str(input()) for i in range(N)]

SA=list(set(S))
d=[0]*len(SA)
for i in range(len(SA)):
  d[i]=S.count(SA[i])

MAX=[i for i, v in enumerate(d) if v == max(d)]

SB=[]
for i in MAX:
  SB.append(SA[i])

SB.sort()
for i in SB:
  print(i)

### FIXED CODE ###

import collections
N=int(input())
S=[]
for i in range(N):
   S.append(str(input())) 
c=collections.Counter(S)
c_sorted=sorted(c.items(),key=lambda x:x[0])
s=max(c.values())
for i in c_sorted:
    if i[1]==s:
        print(i[0])
### BUGGY CODE ###

from itertools import product, combinations
import numpy as np

N = int(input())

dp = np.zeros(shape=(N, N), dtype=int)

for i in range(N):
    dp[i] = np.array(list(map(int, input().split(' '))))

original = dp.copy()

for k, i in product(range(N), repeat=2):
    dp[i] = np.minimum(dp[i], dp[i][k] + dp[k])

if np.all(dp == original):
    route_set = set()
    costs = []
    for i in range(N):
        for j in range(i + 1, N):
            route_set.add(dp[i][j])
            costs.append(dp[i][j])

    route_set = route_set - set(map(sum, combinations(costs, r=2)))
    print(sum([cost for cost in costs if cost in route_set]))
else:
    print(-1)


### FIXED CODE ###

import copy
from itertools import product, combinations

N = int(input())

dp = []
for _ in range(N):
    dp.append(list(map(int, input().split(' '))))

original = copy.deepcopy(dp)

for k, i, j in product(range(N), repeat=3):
    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

if dp == original:
    cost = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                if k == i or k == j:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    break
            else:
                cost += dp[i][j]
    print(cost)
else:
    print(-1)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [list(map(int, input().split())) for _ in range(M)]

A = sorted(A)
for i in range(M):
  for j in range(B[i][0]):
    if B[i][1] > A[0]:
      A[0] = B[i][1]
      A = sorted(A)
      
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
D = [(A[i], 1) for i in range(N)]

for i in range(M):
  B, C = (map(int, input().split()))
  D.append((C, B))
  
D.sort()
D.reverse()

ans, left = 0, N
for (i, j) in D:
    use = min(j, left)
    ans += use * i
    left -= use
print(ans)
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split()) # ノード数, エッジ数
edges = [set(map(int, input().split())) for i in range(M)] # エッジ
que = deque([1]) # 探索用キュー
ans = [0] + [-1 for i in range(N - 1)] # 未探索ノード 兼 道しるべ

while -1 in ans: # 未探索ノードがある間
    node = que.popleft() # キューから取り出し
    for edge in edges: # 全てのエッジに対して
        if node in edge: # 現在のノードを含むなら
            neighbor = (edge - {node}).pop() # 隣接ノードを確認
            if ans[neighbor - 1] == -1: # 隣接ノードが未探索なら
                ans[neighbor - 1] = node # 道しるべを設定
                que.append(neighbor) # キューに入れる

print('Yes')
for a in ans[1:]:
    print(a)


### FIXED CODE ###

# 入力
N, M = map(int, input().split()) # ノード数, エッジ数
edges = [[] for i in range(N)] # エッジ
for i in range(M):
    A, B = map(int, input().split())
    edges[A - 1] += [B - 1]
    edges[B - 1] += [A - 1]

# 幅優先探索
que = [0] # 探索用キュー
ans = [0] + [-1 for i in range(N - 1)] # 未探索ノード 兼 道しるべ
while -1 in ans: # 未探索ノードがある間
    quetmp = que
    que = []
    for node in quetmp: # 探索キュー内のノードに対して
        for neighbor in edges[node]: # 全ての隣接ノードに対して
            if ans[neighbor] == -1: # 未探索なら
                ans[neighbor] = node + 1 # 道しるべを設定
                que += [neighbor] # キューに入れる

# 出力
print('Yes')
for a in ans[1:]:
    print(a)
### BUGGY CODE ###

n = int(input())
numList = []
for i in range(n):
  numList.append(int(input()))

workList = numList.copy()
for j in range(n):
  workList.remove(numList[j])
  print(max(set(workList)))
  workList = numList.copy()

### FIXED CODE ###

n = int(input())
numList  = [int(input()) for i in range(n)]
maxVal = max(numList)
workList = numList[:]
workList.remove(maxVal)
secondVal = max(workList)
for num in numList:
  if num != maxVal:
    print(maxVal)
  else:
    print(secondVal)
### BUGGY CODE ###

n = int(input())
ans = [0 for i in range(n)]
for i in range(6,n+1):
  for x in range(1,101):
    for y in range(1,101):
      for z in range(1,101):
        if x**2+y**2+z**2+x*y+y*z+z*x == i:
          ans[i-1]+=1
for i in ans:
  print(i)

### FIXED CODE ###

n = int(input())
ans = [0 for i in range(10001)]
for x in range(1,101):
  for y in range(1,101):
    for z in range(1,101):
      v = x**2+y**2+z**2+x*y+y*z+z*x
      if v<=10000:
        ans[v]+=1
for i in range(n):
  print(ans[i+1])
### BUGGY CODE ###

l = input()

a3 = [3**i for i in range(len(l)+5)]
a2 = [2**i for i in range(len(l)+5)]

ans = 0
a = 0
for i in range(len(l)):
    if l[i]=='1':
        ans += (a3[len(l)-i-1]*a2[a])
        a+=1
    if i==len(l)-1:
        ans += a2[a]
    ans %= 10**9+7

print(ans)


### FIXED CODE ###

l = input()

a3 = [1]
a2 = [1]

for i in range(len(l)+5):
    a3.append((a3[-1]*3)%(10**9+7))
    a2.append((a2[-1]*2)%(10**9+7))

ans = 0
a = 0
for i in range(len(l)):
    if l[i]=='1':
        ans += (a3[len(l)-i-1]*a2[a])
        a+=1
    if i==len(l)-1:
        ans += a2[a]
    ans %= 10**9+7

print(ans)
### BUGGY CODE ###

import queue

n,m = map(int, input().split())
routs = [[] for i in range(n + 1)]
for i in range(m):
    a, b = map(int,input().split())
    routs[a].append(b)
    routs[b].append(a)

parent = [-1] * (n-1)
visit = ["yet"]*(n)
visit[0] = "done"
q = queue.Queue()
q.put(1)
while -1 in parent:
    temp = q.get()
    for i in routs[temp]:
        if visit[i-1] == "yet":
            q.put(i)
            if parent[i-2] == -1:
                parent[i-2] = temp
            visit[i-1] = "done"
print("Yes")
for i in parent:
    print(i)    
    

### FIXED CODE ###

import queue

n,m = map(int, input().split())
routs = [[] for i in range(n + 1)]
for i in range(m):
    a, b = map(int,input().split())
    routs[a].append(b)
    routs[b].append(a)

parent = [-1] * (n-1)
visit = ["yet"]*(n)
visit[0] = "done"
q = queue.Queue()
q.put(1)
while not q.empty():
    temp = q.get()
    for i in routs[temp]:
        if visit[i-1] == "yet":
            q.put(i)
            if parent[i-2] == -1:
                parent[i-2] = temp
            visit[i-1] = "done"

print("Yes")
for i in parent:
    print(i)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []

for i in range(1,n+1):
  for j in range(n):
    if a[j] == i:
      b.append(a.index(i) + 1)
      break
      
print(' '.join(map(str, b)))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0 for j in range(n)]

for i in range(n):
    b[a[i]-1] = i+1

print(*b)
### BUGGY CODE ###

import bisect

n = int(input())
abl = [list(map(int,input().split())) for nesya in range(n)]
al = []
bl = []
for ab in abl:
  bisect.insort_left(al,ab[0])
  bisect.insort_left(bl,ab[1])
if n%2 == 1:
  z = (n+1)//2-1
  print(bl[z]-al[z]+1)
else:
  x = n//2
  ax2 = al[x-1]+al[x]
  bx2 = bl[x-1]+bl[x]
  print(bx2-ax2+1)

### FIXED CODE ###

from statistics import median

n = int(input())
abl = [list(map(int,input().split())) for nesya in range(n)]
al = []
bl = []
for ab in abl:
  al.append(ab[0])
  bl.append(ab[1])
if n%2 == 1:
  print(median(bl)-median(al)+1)
else:
  print(int(median(bl)*2-median(al)*2+1))