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

from collections import deque
import sys
sys.setrecursionlimit(10**7)

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
P=[-1]*M
def bfs(u):
  P[u]=0
  queue=deque([u])
  while queue:
    v=queue.popleft()    
    for i in D[v]:
      P[i]=P[v]+1
      queue.append(i)
for i in range(M):
  if len(F[i])==0:
    bfs(i)
if min(P)==-1:
  print(-1)
else:
  print(max(P)+1)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**7)

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
    
q=deque()
P=[0]*M
for i in range(M):
  if len(F[i])==0:
    q.append((i,0))

r=[]
while q:
  v1,cnt=q.popleft()
  r.append((v1,cnt))
  for v2 in D[v1]:
    P[v2]+=1
    if P[v2]==len(F[v2]):
      q.append((v2,cnt+1))

if len(r)!=M:
  print(-1)
else:
  print(r[-1][-1]+1)
### BUGGY CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    inp = []
    for i in range(n):
        inp.append(list(input()))
    ans = 0
    p_all = set([(x, y) for x in range(n) for y in range(n)])
    for i in range(n):
        p = [(x, y) for x in range(n - i) for y in range(n - i) if (x, y) in p_all]
        for x, y in p:
            if inp[y][x] == ".":
                pp = [(xx, yy) for xx in range(x, x + i + 1) for yy in range(y, y + i + 1)]
                for xx, yy in pp:
                    if inp[yy][xx] == "*":
                        p_all.remove((x, y))
                        break
                else:
                    ans = i + 1
                    break
        else:
            continue
    print(ans)



### FIXED CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    inp = []
    for i in range(n):
        inp.append(list(input()))
    
    sq_max = [[0 for i in range(n + 1)] for j in range(n + 1)]
    
    for y in range(n):
        for x in range(n):
            if inp[y][x] == ".":
                sq_max[y + 1][x + 1] = min(sq_max[y][x + 1], sq_max[y + 1][x], sq_max[y][x]) + 1
            else:
                sq_max[y + 1][x + 1] = 0
    ans = max(map(max, sq_max))
    print(ans)
### BUGGY CODE ###

import numpy as np

def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j >= a[i]:
                dp[j] = min(dp[j], dp[j-a[i]] + b[i])
    return min(dp[H:Hmax+1])


H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = np.full(Hmax+1, INF, dtype=int)
dp[0] = 0
print(rec_z())

### FIXED CODE ###

def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j >= a[i]:
                dp[j] = min(dp[j], dp[j-a[i]] + b[i])
    return min(dp[H:Hmax+1])
 
 
H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = [INF for _ in range(Hmax+1)] 
dp[0] = 0
print(rec_z())
### BUGGY CODE ###

s = input()

t, a = 0, 1
mod = [0]*2019
mod[0] = 1
s = s[::-1]
n = len(s)
for i in range(n):
    t = (t + int(s[i]) * a) % 2019
    a *= 10
    mod[t] += 1
ans = 0

for i in range(2019):
    ans += mod[i]*(mod[i]-1)//2
print(ans)

### FIXED CODE ###

s = input()
#s = '9' * 200000

mod = [1] + [0]*2018
t = 0
a = 1
n = len(s)
s = s[::-1]
for i in range(n):
    t = (t + int(s[i])*a) % 2019
    a = a * 10 % 2019
    mod[t] += 1
ans = 0
for i in range(2019):
    ans += mod[i]*(mod[i]-1)//2
print(ans)
### BUGGY CODE ###

def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    S = list(input())
    Sint = [1 if c == 'A' else 2 if c=='B' else 3 for c in S]
    N = len(S)

    ans = 0
    for i in range(N-2):
        if Sint[i] == 1 and Sint[i+1] == 2 and Sint[i+2] == 3:
            ans += 1
            Sint[i],Sint[i+1],Sint[i+2] = 2,3,1
            for j in range(i-1,-1,-1):
                if Sint[j] == 1:
                    ans += 1
                    Sint[j],Sint[j+1],Sint[j+2] = 2,3,1
                else:
                    break
    print(ans)



    
main()

### FIXED CODE ###

def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    S = list(input())
    S = [1 if c == 'A' else 2 if c=='B' else 3 for c in S]
    N = len(S)
    ans = 0
    continuous_one = 0
    i = 0

    while i < N-1:
        if S[i] == 1:
            continuous_one += 1
            i += 1
        elif S[i] == 2 and S[i+1] == 3:
            ans += continuous_one
            i += 2
        else:
            continuous_one = 0
            i += 1
    

    



    print(ans)



    
main()
### BUGGY CODE ###

n=int(input())
ans=1
a=list(map(int,input().split()))
for i in range(n):
    ans*=a[i]
    if 0 in a:
        ans=0
        break
    if ans>1000000000000000000:
        ans=-1
        break
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
flag=0
ans=0
if 0 in a:
    flag=1
if flag==0:
    ans=1
    for i in range(n):
        ans*=a[i]
        if ans>1000000000000000000:
            flag=-1
            break
if flag==-1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import collections
n = int(input())
s = [input() for _ in range(n)]
D = []

c = collections.Counter(s)

for i in range(len(c.most_common())):
    if c.most_common()[i][1] == c.most_common()[0][1]:
        d = c.most_common()[i][0]
        D.append(d)
    else:
        break

e = sorted(D)

for i in e:
    print(i)

### FIXED CODE ###

N = int(input())
A = {}
for i in range(N):
  s = input()
  if s in A:
    A[s] += 1
  else:
    A[s] = 1
s_max = max(A.values())
for j in sorted(k for k in A if A[k] == s_max):
  print(j)
### BUGGY CODE ###

import itertools
L, R = map(int, input().split())
 
remainder_list = [N%2019 for N in range(L, R+1)]
remainder_list = list(set(remainder_list))
all_list = [(i*j)%2019 for i, j in list(itertools.combinations(remainder_list, 2))]
print(min(all_list))

### FIXED CODE ###

import itertools
L, R = map(int, input().split())

if R - L + 1 > 2019:
    remainder_list = [N%2019 for N in range(L, L+2019)]
else:
    remainder_list = [N%2019 for N in range(L, R+1)]  
remainder_list = list(set(remainder_list))
all_list = [(i*j)%2019 for i, j in list(itertools.combinations(remainder_list, 2))]
print(min(all_list))
### BUGGY CODE ###

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def query(n: int):
    print(n)
    res = input()
    if res == "Vacant":
        sys.exit()
    return res


def main():
    n = input_int()
    record = [None] * n
    # 方針：
    # 2分探索で探す
    # 初期状態を見つける
    left = 0
    right = n - 1
    record[left] = query(left)
    record[right] = query(right)

    while True:
        mid = (left + right) // 2
        record[mid] = query(mid)
        if (mid - left) % 2 == 1:
            # 差が奇数で性別が一致する場合は空白が間に存在する
            if record[left] == record[mid]:
                right = mid
            else:
                left = mid
        else:
            # 差が偶数で性別が一致する場合は空白が間に存在しない
            if record[left] == record[mid]:
                left = mid
            else:
                right = mid

    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def query(n: int):
    print(n, flush=True)
    res = input().rstrip()[0]
    if res == "V":
        sys.exit()
    return res


def main():
    n = input_int()
    record = [None] * n
    # 方針：
    # 2分探索で探す
    # 初期状態を見つける
    left = 0
    right = n - 1
    record[left] = query(left)
    record[right] = query(right)

    for i in range(18):
        mid = (left + right) // 2
        record[mid] = query(mid)
        if (mid - left) % 2 == 1:
            # 差が奇数で性別が一致する場合は空白が間に存在する
            if record[left] == record[mid]:
                right = mid
            else:
                left = mid
        else:
            # 差が偶数で性別が一致する場合は空白が間に存在しない
            if record[left] == record[mid]:
                left = mid
            else:
                right = mid

    return


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

from fractions import gcd
import time
n = int(input())
a = list(map(int, input().split()))
t1 = time.time()
mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
g = 1
flag = 1
for i in range(n):
    g = a[i] * g // gcd(a[i], g)
    #g %= mod
    t2 = time.time()
    if t2 - t1 > 0.5:
        flag = 0
        break

if flag == 1:
    ans = 0
    for i in range(n):
        ans += g * modinv(a[i])
        ans %= mod
    print(ans)

else:
    ans = 0

    for i in range(n):
        g = 1
        for j in range(n):
            if i == j:
                continue
            else:
                g *= a[j]
                g %= mod
        ans += g
    print(ans%mod)


### FIXED CODE ###

from fractions import gcd #直して
n = int(input())
a = list(map(int, input().split()))

mod = 10**9+7
l = 1
for i in range(n):
    l = a[i] // gcd(l, a[i]) * l
    

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

d = 0
for i in range(n):
    d += modinv(a[i])

print((l*d) % mod)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
  a.append(int(input())-1)
i=0

out=0

while i!=1:
  out+=1
  i=a[i]
  if i>n:
    out=-1
    break

print(out)


### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
  a.append(int(input())-1)
i=0

out=0
kai=0
while i!=1:
  kai+=1
  out+=1
  i=a[i]
  if kai>n:
    out=-1
    break

print(out)
### BUGGY CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[0]*60
ans=0
mod=10**9+7
for i in range(n):
  a=str(bin(A[i]))[2:].zfill(60)
  for j in range(60):
    if a[j]=="0":
      ans=(ans+B[j]*(pow(2,(59-j),mod)))%mod
    else:
      ans=(ans+(i-B[j])*pow(2,(59-j),mod))%mod
      B[j]+=1
print(ans)


### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[0]*60
C=[0]*60
ans=0
mod=10**9+7
for i,a in enumerate(A):
  for j in range(60):
    if a%2==0:
      C[j]+=B[j]
    else:
      C[j]+=i-B[j]
      B[j]+=1
    a//=2
for i in range(60):
  ans=(ans+C[i]*(pow(2,i,mod)))%mod
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
dp=[10**9]*n
dp[0]=0
dp[1]=abs(a[1]-a[0])
for i in range(2,n):
    for j in range(max(0,i-k),i):
        dp[i]=min(dp[j]+abs(a[i]-a[j]),dp[i])
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
dp=[10**9]*n
dp[0]=0
dp[1]=abs(a[1]-a[0])
for i in range(2,n):
    for j in range(max(0,i-k),i):
        dp[i]=min(dp[j]+abs(a[i]-a[j]),dp[i])
print(dp[-1])
### BUGGY CODE ###

import sys

from collections import defaultdict

I=sys.stdin.readline

n=int(I())
arr=sorted(list(map(int,I().split())))
d=defaultdict(int)

for i in arr:
	d[i]+=1

ans=0
visited=[0]*(10**6+1)
for i in arr:
	if d[i]==1 and visited[i]==0:
		ans+=1

	for j in range(i,10**6+1,i):
		visited[j]=1

print(ans)


### FIXED CODE ###

import sys

from collections import defaultdict

I=sys.stdin.readline

n=int(I())
arr=sorted(list(map(int,I().split())))
d=defaultdict(int)

for i in arr:
	d[i]+=1

ans=0
visited=[0]*(arr[-1]+1)
for i in arr:
	if d[i]==1 and visited[i]==0:
		ans+=1

	for j in range(i,arr[-1]+1,i):
		visited[j]=1

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

s = input()
q = int(input())
query = [input() for i in range(q)]

for i in range(q):
  temp = query[i].split()
  if int(temp[0]) == 1:
    s = ''.join(list(reversed(s)))
  else:
    if int(temp[1]) == 1:
      s = '{}{}'.format(temp[2], s)
    else:
      s = '{}{}'.format(s, temp[2])

print(s)


### FIXED CODE ###

from collections import deque

def main():
  rev = False
  s = deque(input())
  q = int(input())
  query = tuple(input() for i in range(q))

  for i in range(q):
    temp = query[i].split()
    if int(temp[0]) == 1:
      rev = not rev
    else:
      if (int(temp[1]) == 1 and (not rev)) or (int(temp[1]) == 2 and rev):
        s.appendleft(temp[2])
      else:
        s.append(temp[2])

  if rev:
    s.reverse()

  print(''.join(s))

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

N = int(input())
 
num = []
for i in range(N):
  num.append(int(input()))
  
num = sorted(num)
ans = [num[0]]
num.pop(0)
 
for i in range(len(num)-1):
  if i % 4 == 0:
    ans.append(num[-1])
    num.pop(-1)
  elif i % 4 == 1:
    ans.insert(0,num[-1])
    num.pop(-1)
  elif i % 4 == 2:
    ans.append(num[0])
    num.pop(0)
  else:
    ans.insert(0,num[0])
    num.pop(0)
 
answer = max(abs(num[0]-ans[0]), abs(num[0]-ans[-1]))
for i in range(len(ans)-1):
  answer += abs(ans[i] - ans[i+1])
  
print(answer)

### FIXED CODE ###

from collections import deque
N = int(input())
 
num = []
for i in range(N):
  num.append(int(input()))
  
num = deque(sorted(num))
ans = deque([num.popleft()])
 
for i in range(N-2):
  if i % 4 == 0:
    ans.append(num.pop())
  elif i % 4 == 1:
    ans.appendleft(num.pop())
  elif i % 4 == 2:
    ans.append(num.popleft())
  else:
    ans.appendleft(num.popleft())

answer = max(abs(num[0]-ans[0]), abs(num[0]-ans[-1]))
for i in range(len(ans)-1):
  answer += abs(ans[i] - ans[i+1])
  
print(answer)
### BUGGY CODE ###

h,w,m=map(int,input().split())
HW=[list(map(int,input().split())) for _ in range(m)]

DP=[[[0,0] for _ in range(w)] for _ in range(h)]
MAP=[["." for _ in range(w)] for _ in range(h)]
for H,W in HW:
    DP[H-1][W-1]=[1,1]
    MAP[H-1][W-1]="#"

for i in range(h):
    for j in range(1,w):
        DP[i][j][0] +=DP[i][j-1][0]

for i in range(w):
    for j in range(1,h):
        DP[j][i][1] +=DP[j-1][i][1]

cnt=0
for i in range(h):
    for j in range(w):
        num=DP[i][w-1][0]+DP[h-1][j][1]
        if MAP[i][j]=="#":num -=1
        cnt=max(cnt,num)
print(cnt)

### FIXED CODE ###

h,w,m=map(int,input().split())
HW=[list(map(int,input().split())) for _ in range(m)]

H,W=[0 for _ in range(h)],[0 for _ in range(w)]
for i,j in HW:
    i,j=i-1,j-1
    H[i] +=1
    W[j] +=1

max_h,max_w=max(H),max(W)
ans=max_h+max_w
cnt=H.count(max_h)*W.count(max_w)
for i,j in HW:
    if H[i-1]==max_h and W[j-1]==max_w:
        cnt -=1
print(ans if cnt!=0 else ans-1)
### BUGGY CODE ###

n = int(input())
x = [int(w) for w in input().split()]

ans = 0
mod = 10**9 + 7
for i in range(n-1):
    for j in range(i+1,n):
        ans += (((x[i])%mod)*(x[j]%mod))%mod
        
print((ans)%mod)

### FIXED CODE ###

n = int(input())
x = [int(w) for w in input().split()]

ans = 0
mod = 10**9 + 7
s = sum(x)

for i in range(n):
    ans += ((x[i])**2)

ans = (s**2 - ans)//2
print(ans%mod)
### BUGGY CODE ###

import math
H,N = map(int,input().split())
A = [int(x) for x in input().split()]

count = 0
sum2 = []
for i in range(2 ** N):
        sum1 = []
        for j in range(len(A)):
            if ( i >> j) & 1 == 1:
                sum1.append(A[j])
        if sum(sum1) == H:
            count = 1
            print("Yes")
            break


if count == 0:
    print("No")


### FIXED CODE ###

import math
H,N = map(int,input().split())
A = [int(x) for x in input().split()]

count = 0
sum2 = []
'''for i in range(2 ** N):
        sum1 = []
        for j in range(len(A)):
            if ( i >> j) & 1 == 1:
                sum1.append(A[j])
        if sum(sum1) == H:
            count = 1
            print("Yes")
            break
'''
if sum(A) >= H:
    print("Yes")

else:
    print("No")
### BUGGY CODE ###

N, M = map(int, input().split())
l, r = map(int, input().split())
s = set(list(range(l, r+1)))
for i in range(1, M):
  l, r = map(int, input().split())
  s1 = set(list(range(l, r+1)))
  s = s & s1
print(len(s))

### FIXED CODE ###

N, M = map(int, input().split())
L_lis = []
R_lis = []
for i in range(M):
  L, R = map(int, input().split())
  L_lis.append(L)
  R_lis.append(R)
new_L, new_R = max(L_lis), min(R_lis)
if new_L <= new_R:
  print(new_R - new_L + 1)
else:
  print(0)
### BUGGY CODE ###

#coding:utf-8
import numpy as np
import collections
N = int(input())
arr = []
for n in range(N):
    arr.append(list(map(int,input().split())))
arr = np.array(arr)
x_min  = arr[:,0].min()
x_max = arr[:,0].max()
y_min = arr[:,1].min()
y_max =  arr[:,1].max()
mx = arr[:,2].max()
for k in range(mx+100,mx-1,-1):
    for i in range(x_min,x_max+1):
        for j in range(y_min,y_max+1):
            for x,y,h in arr:
                if(max(k-abs(i-x)-abs(j-y),0)!=h):
                    break
            else:
                print (i,j,k)
                exit()


### FIXED CODE ###

#coding:utf-8
import numpy as np
import collections
N = int(input())
arr = []
for n in range(N):
    arr.append(list(map(int,input().split())))
narr = np.array(arr)
x_min  = narr[:,0].min()
x_max = narr[:,0].max()
y_min = narr[:,1].min()
y_max =  narr[:,1].max()
mx = narr[:,2].max()
for k in range(mx+100,mx-1,-1):
    for i in range(x_min,x_max+1):
        for j in range(y_min,y_max+1):
            for x,y,h in arr:
                h_ = max(k-abs(i-x)-abs(j-y),0)
                if h_ != h:
                    break
            else:
                print (i,j,k)
                exit()
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [10**6] * 100005
dp[0] = 0
# dp[1] = abs(h[1]-h[0])
for i in range(1, N):
    dp[i] = min(dp[i-j] + abs(h[i-j] - h[i]) for j in range(1,min(K,i)+1))
    # print([dp[i-j] + abs(h[i-j] - h[i]) for j in range(1,min(K,i)+1)])
    # for j in range(1, min(K,i)+1):
    #     dp[i] = min(dp[i], dp[i-j] + abs(h[i-j] - h[i]))

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [10**6] * 100005
dp[0] = 0
# dp[1] = abs(h[1]-h[0])
for i in range(1, N):
    dp[i] = min(dp[i-j] + abs(h[i-j] - h[i]) for j in range(1,min(K,i)+1))
    # print([dp[i-j] + abs(h[i-j] - h[i]) for j in range(1,min(K,i)+1)])
    # for j in range(1, min(K,i)+1):
    #     dp[i] = min(dp[i], dp[i-j] + abs(h[i-j] - h[i]))

print(dp[N-1])
### BUGGY CODE ###

def BinSearch(A, hi, lo):
    b = (hi + lo) // 2
    tmp0 = FindAns(A, b - 1)
    tmp1 = FindAns(A, b)
    if hi == lo:
        tmp2 = FindAns(A, b + 1)
        return min(tmp0, tmp1, tmp2)
    if tmp0 < tmp1:
        return BinSearch(A, b - 1, lo)
    else:
        return BinSearch(A, hi, lo + 1)
    
def FindAns(A, b):
    ans = 0
    for a in A:
        ans += abs(a - b)
    return ans

n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    A[i] -= i + 1
A = sorted(A)
hi = A[int(len(A) / 2 + 1) if int(len(A) / 2 + 1) <  len(A)  else int(len(A) / 2)]
lo = A[int(len(A) / 2 - 1) if int(len(A) / 2 - 1) >= 0 else int(len(A) / 2)]

print(BinSearch(A, hi, lo))

### FIXED CODE ###

def BinSearch(A, hi, lo):
    b = (hi + lo) // 2
    tmp0 = FindAns(A, b - 1)
    tmp1 = FindAns(A, b)
    if hi == lo:
        tmp2 = FindAns(A, b + 1)
        return min(tmp0, tmp1, tmp2)
    if tmp0 < tmp1:
        return BinSearch(A, b - 1, lo)
    else:
        return BinSearch(A, hi, b + 1)
    
def FindAns(A, b):
    ans = 0
    for a in A:
        ans += abs(a - b)
    return ans

n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    A[i] -= i + 1
    
hi = max(A)
lo = min(A)

print(BinSearch(A, hi, lo))
### BUGGY CODE ###

from collections import defaultdict
from itertools import combinations

N = int(input())
S = input()
Q = int(1e9 + 7)

d = defaultdict(int)
keys = set()

for s in S:
    d[s] += 1
    keys.add(s)

ans = 0

for i in range(0, len(keys)):
    for c in combinations(keys, i+1):
        n = 1
        for k in c:
            n *= d[k]
        ans += n
        ans %= Q

print(ans)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = input()
Q = int(1e9 + 7)

d = defaultdict(int)

for s in S:
    d[s] += 1

ans = 1
for k, v in d.items():
    ans *= (v + 1)
    ans %= Q
ans -= 1
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
A_s = list(map(int,input().split()))
for _ in range(M):
  B,C = map(int,input().split())
  A_s.extend([C] * B)
A_s = sorted(A_s)
print(sum(A_s[-N:]))


### FIXED CODE ###

N,M = map(int,input().split())
A_s = list(map(int,input().split()))
BC_s = []
for _ in range(M):
  tempB,tempC = map(int,input().split())
  BC_s.append([tempB,tempC])
BC_s = reversed(sorted(BC_s, key=lambda x:x[1]))
D = []
A_s = sorted(A_s)

A_s_size = N
for BC in BC_s:
    B = BC[0]
    C = BC[1]
    if A_s_size == 0:
        break
    elif A_s_size < B:
        D.extend([C]*A_s_size)
        A_s_size -= A_s_size
    else:
        D.extend([C]*B)
        A_s_size -= B
minLength = min(N,len(D))
for i in range(minLength):
    if A_s[i] < D[i]:
        A_s[i] = D[i]
    else:
        break
print(sum(A_s[-N:]))
### BUGGY CODE ###

N,M = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i],B[i] = map(lambda x:int(x)-1,input().split())

def check_connect(connect,cnt,A,B):
    a = cnt[A]
    b = cnt[B]
    if a == b:
        return connect,0,cnt
    tmp1 = len(connect[a])
    tmp2 = len(connect[b])
    connect[a] = connect[a] | connect[b]
    for i in connect[b]:
        cnt[i] = a
    tmp3 = len(connect[a])
    connect[b] = set()
    return connect,(tmp3*(tmp3-1)-tmp1*(tmp1-1)-tmp2*(tmp2-1))//2,cnt

connect = [[] for _ in range(M+1)]
connect[M] = [{i}for i in range(N)]
cnt = [i for i in range(N)]
dfubensa = [0]*M
for i in range(M-1,-1,-1):
    connect[i],dfubensa[i],cnt = check_connect(connect[i+1],cnt,A[i],B[i])

fubensa = [dfubensa[0]]*M
print(fubensa[0])
for i in range(1,M):
    fubensa[i] = fubensa[i-1]+ dfubensa[i]
    print(fubensa[i])

### FIXED CODE ###

N,M = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i],B[i] = map(lambda x:int(x)-1,input().split())

def check_connect(A,B):
    a = cnt[A]
    b = cnt[B]
    if a==-1 and b==-1:
        connect.append([A,B])
        cnt[A] = len(connect)-1
        cnt[B] = cnt[A]
        return 1
    if a == b:
        return 0
    if a == -1:
        a,b,A,B = b,a,B,A
    if b==-1:
        connect[a] += [B]
        cnt[B] = a
        return len(connect[a])-1
        
    tmp1 = len(connect[a])
    tmp2 = len(connect[b])
    if tmp2 > tmp1:
        a,b = b,a
    connect[a] += connect[b]
    for i in connect[b]:
        cnt[i] = a
    tmp3 = tmp1+tmp2
    connect[b] = []
    return (tmp3*(tmp3-1)-tmp1*(tmp1-1)-tmp2*(tmp2-1))//2

connect = []
cnt = [-1]*N
dfubensa = [0]*M
for i in range(M-1,-1,-1):
    dfubensa[i] = check_connect(A[i],B[i])

fubensa = dfubensa[0]
print(fubensa)
for i in range(1,M):
    fubensa += dfubensa[i]
    print(fubensa)