Harryxun/stf_run huggingface dataset:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)

mod = 998244353
N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(K)]
A.sort()
dp = BIT(N)
dp.add(1,1)
for i in range(2,N+1):
  for l,r in A:
    if i-l<=0:# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)

mod = 998244353
N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(K)]
A.sort()
dp = BIT(N)
dp.add(1,1)
for i in range(2,N+1):
  for l,r in A:
    if i-l<=0:
      continue
    if i-r>0:
      dp.add(i,dp.get(i-r,i-l)%mod)
    else:
      dp.add(i,dp.sum(i-l)%mod)
print(dp.el[-1]%mod)


      continue
    if i-r>0:
      dp.add(i,dp.get(i-r,i-l)%mod)
    else:
      dp.add(i,dp.sum(i-l)%mod)
print(dp.el[-1]%mod)



### FIXED CODE ###

# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)

mod = 998244353
N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(K)]
A.sort()
dp = BIT(N)
dp.add(1,1)
for i in range(2,N+1):
  for l,r in A:
    if i-l<=0:
      continue
    if i-r>0:
      dp.add(i,dp.get(i-r,i-l)%mod)
    else:
      dp.add(i,dp.sum(i-l)%mod)
print(dp.el[-1]%mod)
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
x=0
def gcd(x,y):
  if x%y==0:
    print(y)
  else:
    return gcd(y,x%y)
  
for i in range(0,n-1):
  for j in range(i+1,n):
    x=gcd(a[i],a[j])
    b.append(x)
    
print(max(b))    
  
  


### FIXED CODE ###

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

l=[]
l.append(0)
l.append(0)
r=[]
r.append(a[n-1])
r.append(a[n-1])
g=[]

def gcd(x,y):
  if x%y==0:
    return y
  else:
    return gcd(y,x%y)


for i in range(1,n):
  l.append(gcd(l[i],a[i-1]))
  r.append(gcd(r[i],a[n-1-i]))
  
r[0]=l[n]

for j in range(0,n):
  g.append(gcd(l[j+1],r[n-j-1]))

print(max(g))
n,k = map(int,input().split())
a = list(map(int,input().split()))
p = a[0]
s = a[0]
g = []
q = []
for i in range(n+1):
    g.append(p)
    p = a[p-1]
g.reverse()
for i in range(n):
    if g[0] == g[i+1]:
        mod = i+1
        break
for i in range(k%3):
    q.append(s)
    s = a[s-1]
print(q[-1])

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
p = a[0]
s = a[0]
g = [1]
q = []
for i in range(n+1):
    g.append(p)
    p = a[p-1]
g.reverse()
for i in range(n):
    if g[0] == g[i+1]:
        mod = i+1
        break
g.reverse()
for i in range(len(g)):
    if g[i] == g[i + mod]:
        d = i
        break
if k <= n:
    for i in range(k):
        q.append(s)
        s = a[s-1]
    q.reverse()
    print(q[0])
else:
    print(g[d+(k-d)%mod])
a = str(input())
s = int(input())

if a<3200:
  print('red')
else:
  print(s)


### FIXED CODE ###

a = int(input())
s = str(input())

if a<3200:
  print('red')
else:
  print(s)
s = input()
n = len(s)
ans = [0] *n 

left = 0
i = 0

while(left<n):
  while s[i]=="R":
    i+=1
  right=i
  while s[right]=="L":
    right +=1
    if right==n-1:
      right += 1
      break

  for k in range(left, right):
    if (i-k) % 2==0:
      ans[i] += 1
    else:
      ans[i-1] += 1

  left = right
  i = left
print(*ans)




### FIXED CODE ###

s = input()
n = len(s)
ans = [0] *n 

left = 0
i = 0

while(left<n-1):
  while s[i]=="R":
    i+=1
  right=i
  while s[right]=="L":
    if right==n-1:
      right += 1
      break        
    right +=1

  for k in range(left, right):
    if (i-k) % 2==0:
      ans[i] += 1
    else:
      ans[i-1] += 1

  left = right
  i = left
    
print(*ans)
from itertools import accumulate
n = int(input())
s = input()

r_acc = list(accumulate([s[i] == 'R' for i in range(n)], initial=0))
g_acc = list(accumulate([s[i] == 'G' for i in range(n)], initial=0))
b_acc = list(accumulate([s[i] == 'B' for i in range(n)], initial=0))

ans = 0
all = {'R', 'G', 'B'}
for i in range(n):
    for j in range(i + 1, n):
        si = s[i]
        sj = s[j]
        if si == sj:
            continue
        if (si == 'R' and sj == 'G') or (si == 'G' and sj == 'R'):
            ans += b_acc[n] - b_acc[j]
            if n >= j + j - i + 1:
                ans -= b_acc[j + j - i + 1] - b_acc[j + j - i]
        elif (si == 'R' and sj == 'B') or (si == 'B' and sj == 'R'):
            ans += g_acc[n] - g_acc[j]
            if n >= j + j - i + 1:
                ans -= g_acc[j + j - i + 1] - g_acc[j + j - i]
        else:
            ans += r_acc[n] - r_acc[j]
            if n >= j + j - i + 1:
                ans -= r_acc[j + j - i + 1] - r_acc[j + j - i]
print(ans)


### FIXED CODE ###

from itertools import accumulate
n = int(input())
s = input()

r_acc = [0] + list(accumulate([int(s[i] == 'R') for i in range(n)]))
g_acc = [0] + list(accumulate([int(s[i] == 'G') for i in range(n)]))
b_acc = [0] + list(accumulate([int(s[i] == 'B') for i in range(n)]))

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        si = s[i]
        sj = s[j]
        if si == sj:
            continue
        if (si == 'R' and sj == 'G') or (si == 'G' and sj == 'R'):
            ans += b_acc[n] - b_acc[j]
            if n >= j + j - i + 1:
                ans -= b_acc[j + j - i + 1] - b_acc[j + j - i]
        elif (si == 'R' and sj == 'B') or (si == 'B' and sj == 'R'):
            ans += g_acc[n] - g_acc[j]
            if n >= j + j - i + 1:
                ans -= g_acc[j + j - i + 1] - g_acc[j + j - i]
        else:
            ans += r_acc[n] - r_acc[j]
            if n >= j + j - i + 1:
                ans -= r_acc[j + j - i + 1] - r_acc[j + j - i]
print(ans)
N,Q = map(int,input().split())
ab = []
a=[]
for n in range(N-1):
    ab.append([int(i) for i in input().split()])
px = []
for q in range(Q):
    px.append([int(i) for i in input().split()])
class Graph():
    def __init__(self):
        """ ノードのつながりを辞書型で表現する """
        self.adjacency_dict = {}
    
    def add_vertex(self, v):
        """ ノードを追加する """
        self.adjacency_dict[v] = []
    def add_edge(self, v1, v2):
        """ ノード同士をつなぐ。"""
        # 無向グラフの場合は双方向。もし有向グラフなら片側のみ。
        self.adjacency_dict[v1].append(v2)    
    def print_graph(self):
        print(self.adjacency_dict)
graph = Graph()
for n in range(N-1):
    if graph.adjacency_dict.get(ab[n][0]):
        pass
    else:
        graph.add_vertex(ab[n][0])
    graph.add_edge(ab[n][0],ab[n][1])
def search(graph,j,ret):
    if graph.get(j):
        for k in graph[j]:
            ret.append(k)
            search(graph,k,ret)
    return ret
values = [0]* N
for q in range(Q):
    add_list = search(graph.adjacency_dict,px[q][0],[px[q][0]])
    for add in add_list:
        values[add-1] += px[q][1]
print(' '.join(map(str, values)))

### FIXED CODE ###

N,Q = map(int,input().split())
AB = [[] for _ in range(N-1)]
for n in range(N-1):
    AB[n] = list(map(int,input().split()))
PX = [[] for _ in range(Q)]
for q in range(Q):
    PX[q] = list(map(int,input().split()))
graph = [[] for _ in range(N+1)]
for ab in AB:
    graph[ab[0]].append(ab[1])
    graph[ab[1]].append(ab[0])
val = [0] * (N+1)
for px in PX:
    val[px[0]] += px[1]
parent = [0] * (N+1)
from collections import deque
Q  = deque([1])
while Q:
    q = Q.popleft()
    for c in graph[q]:
        if c == parent[q]:
            continue
        parent[c] = q
        Q.append(c)
        val[c] += val[q]
print(*val[1:])
n = int(input())
m = int(input())
l1 = []
for i in range (m):
    a1 = int(input())
    l1.append(a1)
s = sum(l1)
r = n - s
if r >= 0:
    print(r)
else:
    print("-1")

### FIXED CODE ###

n, m = map(int, input().split())
ai = map(int, input().split())
li = map(int, list(ai))
s = sum(li)
r = (n - s)
if r >= 0:
    print(r)
else:
    print("-1")
n=int(input())
arr=[int(x) for x in input().split(' ')]
arr2=sorted(arr)
for x in range(n):
  if x+1==arr[x]:
    continue
  else:
    swap(arr[x],arr[arr[x]-1])
    break
if arr==arr2:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

n=int(input())
arr=[int(x) for x in input().split(' ')]
arr2=sorted(arr)
for x in range(n):
	if x+1==arr[x]:
		continue
	else:
		t=arr[x]
		arr[x]=arr[t-1]
		arr[t-1]=t
		break
# print(arr,arr2)
if arr==arr2:
	print("YES")
else:
	print("NO")
import itertools

n, m = map(int, input().split())

x = list(map(int, input().split()))

x = sorted(x)
sum = 0
min = 1000000
flag = False
if m == 1:
    flag = True
    min = 0

l = list(range(1, m))

for i in itertools.combinations(l, n-1): # Change the conbination mCn
    if flag == True:
        break
    sum = 0
    for j in range(0, n):
        if j == 0:
            sum += x[i[0]-1] - x[0]
        elif j == n-1:
            sum += x[-1] - x[i[-1]]
        else:
            sum += x[i[j]-1] - x[i[j-1]]
    if sum < min:
        min = sum

print(min)

### FIXED CODE ###

n, m = map(int, input().split())

if n >= m:
    print(0)
    exit()

x = list(map(int, input().split()))
x = sorted(x)
diff = [x[i+1] - x[i] for i in range(0, m-1)]

sort_diff = sorted(diff, reverse=True)

sum = 0

if len(sort_diff) == 0:
    print(0)
    exit()

for i in range(n-1):
    sort_diff.pop(0)

for i in range(len(sort_diff)):
    sum += sort_diff[i]
print(sum)
N = int(input())
X = list(map(int, input().split()))

def calc_power(p):
  P = list(map(lambda x: (x-p)**2, X))
  return sum(P)

power = []
for p in range(min(X), max(X)):
  power.append(calc_power(p))
  
print(min(power))

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
 
def calc_power(p):
  P = list(map(lambda x: (x-p)**2, X))
  return sum(P)
 
power = []
_min = min(X)
_max = max(X)

if _min != _max:
  for p in range(_min, _max):
    power.append(calc_power(p))
  print(min(power))
  
else:
  power = calc_power(_min)
  print(power)
import sys

INF = float('inf')

def rec(i: int):
    #if(i==0):print(i,H[i])
    #if(i>=1):print(i,H[i],H[i-1])
    #if(i>=2):print(i,H[i],H[i-2])
    if dp[i] < INF:
        return dp[i]

    if i==0: return 0
    res = INF

    res = min(res, rec(i-1)+abs(H[i]-H[i-1]))

    if i > 1:
        res = min(res,rec(i-2)+abs(H[i]-H[i-2]))

    dp[i] = res
    return dp[i]

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

dp = [INF] * (N+2)

print(rec(N-1))

#7
#2 9 4 5 1 6 10


### FIXED CODE ###

import sys


N = int(input())

H = list(map(int,input().split()))

dp = [float('inf')]*N

dp[0] = 0
#print(N)
#print(H)
#print(dp)


for i in range(1,N):
    if(i==1):
        dp[1] = abs(H[1]-H[0])
    else:
        dp[i] = dp[i-1]+abs(H[i]-H[i-1])
        if(dp[i] > dp[i-2]+abs(H[i]-H[i-2])):
            dp[i] = dp[i-2]+abs(H[i]-H[i-2])
        #
        #print(i,dp)

print(dp[-1])

#7
#2 9 4 5 1 6 10
a = str(input())
s = ['z','x','c','v','b','n','m','a','s','d','f','g','h','j','k','l','q','w','e','r','t','y','u','i','o','p']
e = append(a)
w = sorted(e)
print(w[a+1])



### FIXED CODE ###

a = str(input())
s = ['z','x','c','v','b','n','m','a','s','d','f','g','h','j','k','l','q','w','e','r','t','y','u','i','o','p']
s.append(a)
s.sort()
Q = s.index(a)
e = int(Q) + 2
print(s[int(e)])
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

n = int(input())

res = 1
for i in range(n):
    a = int(input())
    g = gcd(res, a)
    res = int(res * a / g)

print(res)


### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

n = int(input())

res = 1
for i in range(n):
    a = int(input())
    g = gcd(res, a)
    res = (res // g) * a

print(res)
a,b = map(int,input().split())
if (a + b)%2 = 0:
    print((a+b)/2)
else:
    print("IMPOSSIBLE") 
    

### FIXED CODE ###

a,b = map(int,input().split())
if (a + b)%2 == 0 :
    print(round((a+b)/2))
else:
    print("IMPOSSIBLE")
N,K=map(int,input().split())
t=list(map(int,input().split()))
g=[1]
gs=set(g)
for i in range(N-1):
  if t[g[i]-1] in gs:
    break
  g.append(t[g[i]-1])
  gs.add(t[g[i]-1])
if K>len(g):
  a=g.index(t[g[-1]-1])
  b=len(g)-a
  K=(K-a)%b+a
print(g[K])

### FIXED CODE ###

N, K = map(int, input().split())
T_list = list(map(int, input().split()))
T_list = [T_list[i]-1 for i in range(N)]
point = 0
syuuki = 0

if K < N:
  i = 0
  while i < K:
    point = T_list[point]
    i += 1  

else:
  i = 0
  while i < N:
    point = T_list[point]
    if point == 0:
      syuuki = i+1
      break
    i += 1
  second_point = point
  
  if syuuki != 0:
    L = K % syuuki

  else:
    j = 0
    while j < N:
      point = T_list[point]
      if point == second_point:
        syuuki = j+1
        break
      j += 1
    L = (K-i) % syuuki

  k = 0
  while k < L:
    point = T_list[point]
    k += 1
  
print(point+1)
import numpy as np
import sys 


def main():
    H, W = [int(x) for x in sys.stdin.readline().split()]
    board = [[0 for i in range(H)] for j in range(W)]

    """ #は1, .は0 """
    for i in range(H):
        X = sys.stdin.readline()
        for j in range(len(X)):
            if X[j] == "#":
                board[i][j] = 1

    num_board = np.array(board)
    height, width = num_board.shape[:2]
    count = 0
    height_r, width_r = range(height), range(width)
    while (np.sum(num_board) != height*width):
        num_board_ans = np.zeros((height, width))
        for i in height_r:
            for j in width_r:
                if num_board[i, j] == 1:
                    num_board_ans[i, j] = 1
                    a = max(i-1, 0)
                    num_board_ans[a, j] = 1
                    b = max(j-1, 0)
                    num_board_ans[i, b] = 1
                    c = min(i+1, height-1)
                    num_board_ans[c, j] = 1
                    d = min(j+1, width-1)
                    num_board_ans[i, d] = 1
        num_board = num_board_ans
        count += 1

    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def bfs(h, w, board, visited):
    queue = deque([])
    for i in range(h):
        for j in range(w):
            if board[i][j] == "#":
                queue.append([i, j])
                visited[i][j] = 0
    ans = 0
    while queue:
        y, x = queue.popleft()
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            yn, xn = y+i, x+j
            if yn >= h or xn >= w or yn < 0 or xn < 0:
                continue
            if visited[yn][xn] == -1 and board[yn][xn] == ".":
                visited[yn][xn] = visited[y][x] + 1
                queue.append([yn, xn])
                ans = max(ans, visited[yn][xn])

    return ans


def main():
    h, w = map(int, input().split())
    board = [input() for _ in range(h)]
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    print(bfs(h, w, board, visited))


if __name__ == "__main__":
    main()
n = int(input())
k = [int(x) for x in stdin.readline().rstrip().split()]

k.sort()

ave = round(sum(k) / len(k) )

#print(ave)

def calc_pow(n):
    i = pow(n - ave, 2) 
    return i
  
j = map(calc_pow, k)

print(sum(j))

### FIXED CODE ###

from sys import stdin
 
n = int(input())
k = [int(x) for x in stdin.readline().rstrip().split()]

k.sort()

ave = round(sum(k) / len(k) )

#print(ave)

def calc_pow(n):
    i = pow(n - ave, 2) 
    return i
  
j = map(calc_pow, k)

print(sum(j))
from itertools import groupby

N = int(input())
S = [input() for _ in range(N)]
M = int(input())
T = [input() for _ in range(M)]

def main():
    for t in T:
        if t in S:
            S.remove(t)
    ans = [len(list(group)) for key, group in groupby(S)]
    print(max([0] + ans))

if __name__ == "__main__":
    main()

### FIXED CODE ###

A, B, C = [int(x) for x in input().split()]
ans = 'Yes' if A + B >= C else 'No'
print(ans)
s = int(input())
f = [s]
i = 1
n = s
while(i<=1000001):
  if n % 2 == 0:
    f.append(int(n/2))
  else:
    f.append(3*n+1)
  n = f[i]
  i = i + 1
f_ = list(dict.fromkeys(f))
f.pop(f.index(f_[0]))
print(f.index(f_[0]))

### FIXED CODE ###

s = int(input())
f = []
n = s
while(1):
  f.append(n)
  if n % 2 == 0:
    n = int(n/2)
  else:
    n = 3*n+1
  
  if n in f:
    break
    
print(len(f)+1)
n = int(input())
w = list(map(int, input().split()))
l = []

for i in range(1, n):
  l.append(abs( sum(w[:t]) -sum(w[t:]) ))
  
print(min(l))

### FIXED CODE ###

n = int(input())
w = list(map(int, input().split()))
l = []

for i in range(1, n):
  l.append(abs( sum(w[:i]) -sum(w[i:]) ))
  
print(min(l))
a=input().split()
b=[]

for i in range(3):
  b.append(a[0][i].upper())
  
  
print(b[0]+b[1]+b[2])

### FIXED CODE ###

a=input().split()
b=[]

for i in range(3):
  b.append(a[i][0].upper())
  
  
print(b[0]+b[1]+b[2])
n, k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n - 1)]
p = 10 ** 9 + 7

E = [[] for i in range(n + 1)]

for a, b in A:
    E[a].append(b)
    E[b].append(a)

visited = [False] * (n + 1)

def dfs2(i, k):
    if k > 2:
        return 0
    res = 0
    for v in E[i]:
        res += dfs2(v, k + 1)
    return res + visited[i]

def dfs(i):
    if visited[i]:
        return 1
    b = dfs2(i, 0)
    visited[i] = True
    
    res = k - b
    for v in E[i]:
        res *= dfs(v)
        res %= p

    return res if res > 0 else 0

print(dfs(1))

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

n, k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n - 1)]
p = 10 ** 9 + 7

E = [[] for i in range(n + 1)]

for a, b in A:
    E[a].append(b)
    E[b].append(a)

visited = [False] * (n + 1)

def dfs(i, f, s):
    if visited[i]:
        return 1
    b = f + s
    visited[i] = True
    
    res = k - b
    s = f
    f = 1
    for v in E[i]:
        if visited[v]:
            continue
        res *= dfs(v, f, s)
        res %= p
        s += 1

    return res if res > 0 else 0

print(dfs(1, 0, 0) % p)
r=int(input())
print(3*a*a)

### FIXED CODE ###

r=int(input())
print(3*r*r)
S = list(map(int,input().split()))
N = S[0]
K = S[1]
TDlist = []
for x in range(0,N):
    TDlist.append(list(map(int,input().split())))

sorted_list = sorted(TDlist, key = lambda x: x[1], reverse=True)
kinds = []
seconds =[]
answer = 0

for x in range(0,K):
    if not sorted_list[x][0] in kinds:
        kinds.append(sorted_list[x][0])
    else:
        seconds.append(sorted_list[x][1])
    answer += sorted_list[x][1]

answer += len(kinds)**2
score = answer
max_score = answer

for x in range(K,N):
    if seconds is []:
        break
    if sorted_list[x][0] in kinds:
        continue
    kinds.append(sorted_list[x][0])
    score += (sorted_list[x][1] - seconds[-1]) + (len(kinds)*2 -1)
    max_score = max(score,answer)

answer = max(answer,max_score)

print(answer)

### FIXED CODE ###

N,K = list(map(int,input().split()))
TDlist = []

for x in range(0,N):
    TDlist.append(list(map(int,input().split())))

TDlist= sorted(TDlist, key = lambda x: x[1],reverse=True)
kinds = set()
seconds = []
answer = 0

for x in TDlist[:K]:
    if not x[0] in kinds:
        kinds.add(x[0])
    else:
        seconds.append(x[1])
    answer += x[1]

answer += len(kinds)**2
score = answer

for x in TDlist[K:]:
    if seconds == []:
        break
    if x[0] in kinds:
        continue
    kinds.add(x[0])
    y = seconds.pop()
    score += (x[1] - y) + (len(kinds)*2 -1)
    answer = max(score,answer)

print(answer)
n,a,b=map(int,input().split())
cnt=0
if (b-a)%2 == 0:
  cnt=round(b-(b+a)/2)
  print(cnt)
  exit()
if (b-a)%2 == 1:
  if a==1:
    if b==n:
        c=n-a
    d=round(1+((b-1)-(((b-1)+a)/2)))
    cnt=min(c,d)
    print(cnt)
    exit()
  if b==n:
    if a==1:
        c=b-1
    d=round(1+(b-(b+a+1)/2))
    cnt=min(c,d)
    print(cnt)
    exit()
  if a-1 >= n-b:
    cnt=round(n-a)
    print(cnt)
    exit()
  if a-1 <= n-b:
    cnt=round(b-1)
    print(cnt)
    exit()

### FIXED CODE ###

n,a,b=map(int,input().split())
cnt=0
c=100000000000000000
if (b-a)%2 == 0:
  cnt=b-(b+a)//2
  print(cnt)
  exit()
if (b-a)%2 == 1:
    cnt=min(a-1,n-b)+1+((b-a-1)//2)
    print(cnt)
    exit()
st=input().split()
N=int(st[0]);A=int(st[1]);B=int(st[2]);
print("{0}".format(min(A*N,B))

### FIXED CODE ###

s=input().split()
N=int(s[0]);A=int(s[1]);B=int(s[2])
if (N*A<=B):
    print("{0}".format(N*A))
else:
    print("{0}".format(B))
import numpy as np

def main():
    n = int(input())
    ball = [list(map(int, input().split(' '))) for i in range(n)]
    ball = np.array(ball, dtype=int)
    # print(ball)

    l1 = []
    l2 = []
    for i in range(n):
        for j in range(i, n):
            if i == j: continue
            dis1 = ball[i] - ball[j]
            dis2 = ball[j] - ball[i]
            l1.append(list(dis1))
            l2.append(list(dis2))
    # print(l1, l2)
    # c1 = collections.Counter(l1)
    # c2 = collections.Counter(l2)

    c1 = []
    c2 = []
    for i in range(len(l1)):
        c1.append(l1.count(l1[i]))
        c2.append(l2.count(l2[i]))
    m1 = np.max(np.array(c1, dtype=int))
    m2 = np.max(np.array(c2, dtype=int))

    print(max(1,n-max(m1,m2)))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
from sys import stdin

def main():
    n, k = [int(x) for x in stdin.readline().rstrip().split()]
    if k == 1: print(0)
    else: print(n-k)

if __name__ == "__main__":
    main()
# from collections import deque
from collections import Counter
from scipy.misc import comb
# from scipy.special import comb
from copy import deepcopy

n = int(input())
k = list(map(int, input().split()))
for i in range(len(k)):
    ans = 0
    k_n = deepcopy(k)
    k_n.pop(i)
    c = Counter(k_n)
    for key in c:
        ans += comb(c[key], 2, exact=True)
    print(ans)

### FIXED CODE ###

# from collections import deque
from collections import Counter
from scipy.misc import comb
# from copy import deepcopy

n = int(input())
a = list(map(int, input().split()))
C = Counter(a)
S = 0
for key in C:
    S += comb(C[key], 2, exact=True)

for k in range(n):
    A = a[k]
    print(S - C[A] + 1)