Harryxun/stf_run huggingface dataset:
#encoding utf-8
def main(n,v):
    # n = int(input())
    # v = list(int(i) for i in input().split())
    even_v = []
    odd_v = []

    for i in range(n):
        if i%2 == 0:
            odd_v.append(v[i])
        else:
            even_v.append(v[i])

    odd_dic = {}
    even_dic = {}
    for i in range(len(odd_v)):
        if odd_v[i] in odd_dic.keys():
            odd_dic[odd_v[i]] += 1
        else:
            odd_dic[odd_v[i]] = 1

    for i in range(len(even_v)):
        if even_v[i] in even_dic.keys():
            even_dic[even_v[i]] += 1
        else:
            even_dic[even_v[i]] = 1

    tem_dic = {}
    for k, v in sorted(even_dic.items(), key=lambda x: -x[1]):
        tem_dic[k] = v
    even_dic = tem_dic
    tem_dic = {}
    for k, v in sorted(odd_dic.items(), key=lambda x: -x[1]):
        tem_dic[k] = v
    odd_dic = tem_dic

    # odd_dic = sorted(odd_dic.items(),key=lambda x:x[1])
    # even_dic = sorted(even_dic.items(),key=lambda x:x[1])

    odd_keys = list(odd_dic.keys())
    even_keys = list(even_dic.keys())

    for i in range(len(odd_keys)-1):
        if odd_dic[odd_keys[i]] == odd_dic[odd_keys[i+1]]:
            if odd_keys[i] > odd_keys[i+1]:
                tem = odd_keys[i]
                odd_keys[i] = odd_keys[i+1]
                odd_keys[i+1] = tem

    for i in range(len(even_keys)-1):
        if even_dic[even_keys[i]] == even_dic[even_keys[i+1]]:
            if even_keys[i] > even_keys[i+1]:
                tem = even_keys[i]
                even_keys[i] = even_keys[i+1]
                even_keys[i+1] = tem


    # print(even_dic,odd_dic)
    # print(even_keys,odd_keys)
    if (len(odd_keys) == 1 and len(even_keys) == 1) and odd_keys[0] == even_keys[0]:
        answer = n/2
    elif odd_dic[odd_keys[0]] == even_dic[even_keys[0]]:
        ans1 = n-int(odd_dic[odd_keys[0]])-int(even_dic[even_keys[1]])
        ans2 = n-int(odd_dic[odd_keys[1]])-int(even_dic[even_keys[0]])
        answer = min(ans1, ans2)
    else:
        answer = n-int(odd_dic[odd_keys[0]])-int(even_dic[even_keys[0]])

    print(int(answer))
    # return(int(answer))

if __name__ == "__main__":
    n = int(input())
    v = list(int(i) for i in input().split())
    main(n,v)

### FIXED CODE ###

from collections import Counter
def main(n,v):
    # n = int(input())
    # v = list(map(int, input().split()))
    odd = Counter(v[0::2]).most_common(2) + [(0, 0)]
    even = Counter(v[1::2]).most_common(2) + [(0, 0)]

    n_half = int(n / 2)

    if (len(odd) == 1 and len(even) == 1) and odd[0][0] == even[0][0]:
        ans = n_half
    elif odd[0][0] == even[0][0]:
        ans = min(n_half - odd[0][1] + n_half - even[1][1],\
                n_half - odd[1][1] + n_half - even[0][1])
    else:
        ans = n_half - odd[0][1] + n_half - even[0][1]

    print(ans)
    return 0

if __name__ == "__main__":
    n = int(input())
    v = list(map(int, input().split()))
    main(n,v)
move_num = int(input())
input_char_str = input()

char_list  = [chr(i) for i in range(65, 65+26)]

ans_char = ""
move_number = move_num
for input_char in input_char_str:
    if (char_list.index(input_char)+move_number) < len(char_list):
        ans_char += char_list[char_list.index(input_char)+move_number]
    else:
        char_index = (char_list.index(input_char)+move_number) - len(char_list)
        ans_char += char_list[char_index]
        
print(ans_char)

### FIXED CODE ###

input_day = input()

day_dict = {"SUN":7,
                 "MON":6,
                 "TUE":5,
                 "WED":4,
                 "THU":3,
                  "FRI":2,
                  "SAT":1}

print(day_dict[input_day])
N,M = int(input())
S = [list(map(int, input().split())) for i in range(M)]
for i in range(1,M+1):
  print(S.count('i'))


### FIXED CODE ###

N,M = map(int, input().split())
x = [0]*N
for i in range(M):
  a,b = map(int, input().split())
  x[a-1] += 1
  x[b-1] += 1
for i in range(N):
  print(x[i])
a,b = map(int,input())
if a <= 8 and b <= 8:
    print('Yay!')
else:
    print(':(')

### FIXED CODE ###

a,b=map(int,input().split())
if a <= 8 and b <= 8:
    print('Yay!')
else:
    print(':(')
def kouyaku(a,b):
    aa = max(a,b)
    bb = min(a,b)
    if bb == 0:
        return aa
    else:
        return kouyaku(bb,aa%bb)

N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

ans = 0
for time in T:
    if ans:
        ans = int( ans * time / kouyaku(ans, time) )
    else:
        ans = time
    
print(ans)

### FIXED CODE ###

def kouyaku(a,b):
    aa = max(a,b)
    bb = min(a,b)
    if bb == 0:
        return aa
    else:
        return kouyaku(bb,aa%bb)

N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

T.sort()

ans = T[0]
for time in T:
    kou = kouyaku(ans, time)
    if kou != time:
        ans = ans//kou * time
    
print(ans)
H = int(input())
W = int(input())
name ={}
count = 0
for i in range(H):
  name[i] = input()
  for j in range(W):
    if name[i][j] ==".":
      count = 0
      for k in range(i-1,i+2):
        for l in range(j-1,j+2):
          if name[k][l] == "#":
            count += 1
      name[i][j] = count
for i in range(H):
  print(name[i])
            

### FIXED CODE ###

H,W = map(int,input().split())
board =list()
ans =list()
count = 0
for y in range(H):
  board.append (input())
  ans.append(["#"]*W)
for y in range(H):
  for x in range(W):
    if board[y][x] ==".":
      count = 0
      for y2 in range(y-1,y+2):
        for x2 in range(x-1,x+2):
          if y2<0 or y2>= H:
            continue
          elif x2<0 or x2>= W:
            continue
          else:
            if board[y2][x2] == "#":
              count += 1
      ans[y][x] = count
for y in range(H):
  for x in range(W):
    print(ans[y][x],end="")
  print()
n = int(input())
flag = False
a, b = 0
for i in range(2, 9):
    if(n % i): continue
    else: flag = True
if(flag and (n/i <= 9)): print('Yes')
else: print('No')


### FIXED CODE ###

n = int(input())
ans = 'No'
for i in range(1, 10):
  if n % i == 0 and 1 <= n // i <= 9:
      ans = 'Yes'
      break
print(ans)
s = input().rstrip()
d = ['dream', 'dreamer']
e = ['erase', 'eraser']
ch = d + e

def search_(s, ch):
    if len(s) == 0:
        return True
    if len(s) < len(ch):
        return False
    else:
        if s[:len(ch)] == ch:
            return search(s[len(ch):])
    return False

def search(s):
    if len(s) == 0:
        return True
    if s[0] == 'd' or s[0] == 'e':
        for ci in ch:
            if search_(s, ci):
                return True
    return False

if search(s):
    print('YES')
else:
    print('NO')


### FIXED CODE ###

s = input().rstrip()
d = ['dream', 'dreamer']
e = ['erase', 'eraser']
ch = d + e

st = [s]

def search_(s, st, ch):
    if len(s) == 0:
        return
    if len(s) < len(ch):
        return
    else:
        if s[:len(ch)] == ch:
            st.append(s[len(ch):])

def search(s):
    if len(s) == 0:
        return True
    if s[0] == 'd' or s[0] == 'e':
        for ci in ch:
            if search_(s, ci):
                return True
    return False

while st:
    s = st.pop(0)
    if len(s) == 0:
        print('YES')
        exit()
    if s[0] == 'd' or s[0] == 'e':
        for ci in ch:
            search_(s, st, ci)
print('NO')
a = int (input())
s = int (input())
print(s) if a>>3200 else print("red")

### FIXED CODE ###

a = int (input())
s = input()
print(s) if a >= 3200 else print("red")
S = input()
year = int(S[:4])
month = int(S[5:7])
if year < 2019:
    print('Heisei')
elif year == 2019:
    if month > 4:
        print('TBD')
    else:
        print('Heisei')
else:
    print('TBD'

### FIXED CODE ###

S = input()
year = int(S[:4])
month = int(S[5:7])
if year < 2019:
    print('Heisei')
elif month < 5:
    print('Heisei')
else:
    print('TBD')
import math
n , x = map(int,input().split())

field = [int(i) for i in input().split()]

diff = list(map(lambda a:a-x,field))

ans = diff[0]

for i in diff[1:]:
    ans = math.gcd(i,ans)

print(ans)

### FIXED CODE ###

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

field = [int(i) for i in input().split()]

diff = list(map(lambda a:abs(a-x),field))

def gcd(x,y):
    # print(x,y)
    if x < y:
        x,y = y,x

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

ans = diff[0]


for i in diff[1:]:
    ans = gcd(i,ans)

print(ans)
a,b,k=map(int,input().split())
if a=k:
  print('0',b)
  
elif a>k:
  print(a-k,b)
  
else:
  print('0',b+a-k)
  
  

### FIXED CODE ###

a,b,k=map(int,input().split())
if a>=k:
  print(a-k,b)
  
else:
  print(0,max(0,a+b-k))
n=input()
ans=0

for i in range(1,n+1):
  if len(str(i)) % 2 == 1:
      ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0

for i in range(1, n + 1):
  if len(str(i)) % 2 == 1:
    ans += 1

print(ans)
N = int(input())

for i in range(1:10):
  for j in range(1:10):
    if N == i*j:
      print("Yes")
    elif i*j ==81:
      print("No")

### FIXED CODE ###

N = int(input())

flag =0

for i in range(1,10):
  for j in range(1,10):
    if N == i*j:
      flag = 1

if flag == 1:
  print("Yes")
else:
  print("No")
def main():
    A, B = map(int, input().split())
    if A < 10 and B < 10:
        p = A * B
        print(p)
    else:
        print(p)
main()

### FIXED CODE ###

def main():
    A, B = map(int, input().split())
    if A < 10 and B < 10:
        p = A * B
        print(p)
    else:
        print(-1)
main()
# -*- coding: utf-8 -*-
a, b, c, d = map(int, input().split())
if(c < b):
    if(d <= b):
        if(d <= a):
            time = 0
        else if(c < a):
            time = d - a
        else:
            time = d - c
    else:
        time = b - c
else:
    time = 0
print(time)


### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b, c, d = map(int, input().split())
if(c < b):
    if(d <= b):
        if(d <= a):
            time = 0
        elif(c < a):
            time = d - a
        else:
            time = d - c
    elif (c < a):
        time = b - a
    else:
        time = b - c
else:
    time = 0
print(time)
from collections import deque

N = int(input())
edges = {i: [] for i in range(N)}
for _ in range(M-1):
    x, y, z = map(int, input().split())
    edges[x-1].append((y-1, z%2))
    edges[y-1].append((x-1, z%2))
color = [None]*N

q = deque([(0, 0)])
while q:
    v, c = q.popleft()
    color[v] = c
    for u, w in edges[v]:
        if color[u] is None:
            if w == 0:
                q.append((u, c))
            else:
                q.append((u, c^1))
print(*color, sep='\n')

### FIXED CODE ###

from collections import deque

N = int(input())
edges = {i: [] for i in range(N)}
for _ in range(N-1):
    x, y, z = map(int, input().split())
    edges[x-1].append((y-1, z%2))
    edges[y-1].append((x-1, z%2))
color = [None]*N

q = deque([(0, 0)])
while q:
    v, c = q.popleft()
    color[v] = c
    for u, w in edges[v]:
        if color[u] is None:
            if w == 0:
                q.append((u, c))
            else:
                q.append((u, c^1))
print(*color, sep='\n')
# 2019/08/07

a,b,c,d,e,f=map(int,input().split())

max_a=f//100*a
max_b=f//100*b
min_ab=min(a,b)*100
max_c=(f-min_ab)//c
max_d=(f-min_ab)//d


def solve():
    cnt=0   
    ans=0   
    for i in range(max_a):
        if i*a>f:break
        for j in range(max_b):
            if i==j==0:continue
            if (i*a+j*b)*100>f:break

            for k in range(max_c):
                if (i*a+j*b)*100+k*c>f:break
                for l in range(max_d):
                    if k==l==0:continue
                    if (i*a+j*b)*100+k*c+l*d>f:break
                    w=(i*a+j*b)*100
                    s=k*c+l*d
                    D=s/w
                    if D>e/100:break
                    if cnt<D:
                        ans=(w+s,s)
                        cnt=D
                    if D==e/100:
                        return ans
    return ans
ans=solve()
if ans is None:print(0,0)
else:print(*ans)

### FIXED CODE ###

# 2019/08/07

a,b,c,d,e,f=map(int,input().split())

max_a=f//100*a
max_b=f//100*b
min_ab=min(a,b)*100
max_c=(f-min_ab)//c
max_d=(f-min_ab)//d


def solve():
    cnt=0   
    ans=0   
    for i in range(max_a):
        if i*a>f:break
        for j in range(max_b):
            if i==j==0:continue
            if (i*a+j*b)*100>f:break

            for k in range(max_c):
                if (i*a+j*b)*100+k*c>f:break
                for l in range(max_d):
                    if k==l==0:continue
                    if (i*a+j*b)*100+k*c+l*d>f:break
                    w=(i*a+j*b)*100
                    s=k*c+l*d
                    D=s/w
                    if D>e/100:break
                    if cnt<D:
                        ans=(w+s,s)
                        cnt=D
                    if D==e/100:
                        return ans
    return ans
ans=solve()
if ans==0:
    print(min(a,b)*100,0)
else:print(*ans)
n=int(input())
sum=1
f=0
f2=0
for i in range(0,n):
	a=int(input())
	if  (a==0): 
		f2=1
	sum=sum*a
	if (sum>1000000000000000000):
		f=1;
}
if (f2==1): 
	print("0\n")
else if(f==1):
	print("-1\n")
else:
	print(sum)
	print("\n")

### FIXED CODE ###

N=int(input())
 
A=list(map(int,input().split()))
 
if 0 in A:
    print(0)
else:
    result=1
    for a in A:
        result=result*a
        if result>10**18:
            result=-1
            break
    print(result)
a,b,c = map(int, input().split())
print(f'{c} {a} {b}')

### FIXED CODE ###

a,b,c = map(int, input().split())
print(str(c)+' '+str(a)+' '+str(b))
A,B=map(int,input().split())
print(min(A-2*B),0)

### FIXED CODE ###

A,B=map(int,input().split())
print(max(A-2*B,0))
N=int(input())
A=[int(i) for i in input().split()]

A.sort(reverse=True)

x=0
y=0
for i in range(N):
      if A[0]==A[1]:
          x=A[0]
          A.remove(x)
          A.remove(x)
          break
      else:
          A.remove(A[0])
if len(A)!=0:
    for i in range(len(A)):
        if A[0]==A[1]:
            y=A[0]
            break
        else:
            A.remove(A[0])

print(x*y)

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]

A.sort(reverse=True)

x=0
y=0
for i in range(N-1):
      if A[0]==A[1]:
          x=A[0]
          A.remove(x)
          A.remove(x)
          break
      else:
          A.remove(A[0])
if len(A)>=2:
    for i in range(len(A)-1):
        if A[0]==A[1]:
            y=A[0]
            break
        else:
            A.remove(A[0])

print(x*y)
n=int(input())
a=list(map(int,input().split()))
b=list(set(a))   
if len(b)==1:
    print(b[0])
    exit()
else:
    c=sorted(b)
    x=1
    while x>0:
        v=c[0]
        for i in range(len(c)):
            if i!=0:
                c[i]=c[i]%v
        c.remove(0)
        c=sorted(list(set(c)))
        if len(c)==1:
            print(c[0])
            exit()
        if c[0]==1:
            x=0
print(1)
            
    





### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(set(a))   
if len(b)==1:
    print(b[0])
    exit()
else:
    c=sorted(b)
    x=1
    while x>0:
        v=c[0]
        for i in range(len(c)):
            if i!=0:
                c[i]=c[i]%v
        while 0 in c:
            c.remove(0)
        c=sorted(list(set(c)))
        if len(c)==1:
            print(c[0])
            exit()
        if c[0]==1:
            x=0
print(1)
tmp = input().split()
N = int(tmp[0])

ListG = []

for i in range(N):
    Si = input().split()
    p = Si in ListG
    if not p :
        ListG.append(Si)
    
print(len(ListG))

### FIXED CODE ###

tmp = input().split()
S = int(tmp[0])
W = int(tmp[1])

if W >= S:
    print('unsafe')
else:
    print('safe')
import string
sen = input().lower()

char_dic = {i:0 for i in string.ascii_lowercase}

for j in sen:
    if j in char_dic:
        char_dic[j] += 1
    else:
        pass

for k in string.ascii_letters:
    print("{} : {}".format(k, char_dic[k]))



### FIXED CODE ###

import string, sys
sen = sys.stdin.read().lower()

char_dic = {i:0 for i in string.ascii_lowercase}

for j in sen:
    if j in char_dic:
        char_dic[j] += 1

for k in string.ascii_lowercase:
    print("{} : {}".format(k, char_dic[k]))
import math 


x1, y1, x2, y2 = map(float, raw_input().split())

print sqrt(pow((x2-x1), 2)+pow((y2-y1), 2))

### FIXED CODE ###

from math import sqrt, pow

x1, y1, x2, y2 = map(float, raw_input().split())

print sqrt(pow((x2-x1), 2)+pow((y2-y1), 2))
h, w = map(int, input().split())
s = [['.']*(w+2)]
for _ in range(h):
    s.append(['.'] + list(input()) + ['.'])
s.append(['.']*(w+2))
ans = 'Yes'

for i in range(1, w):
    for j in range(1, h):
        if s[i][j] == '#':
            l = s[i][j-1]
            u = s[i-1][j]
            r = s[i][j+1]
            d = s[i+1][j]
            if l=='.' and u=='.' and r=='.' and d=='.':
                ans = 'No'

print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = ['.' + input() + '.' for _ in range(H)]
S = ['.'*(W+2)] + S + ['.'*(W+2)]

ans = 'Yes'

for i in range(1, H+1):
    for j in range(1, W+1):
        if S[i][j]=='#':
            if S[i-1][j]!='#' and S[i][j-1]!='#' and S[i+1][j]!='#' and S[i][j+1]!='#':
                print('No')
                exit()

print(ans)
M1, M2, D1, D2 = map(int, input().split())

if M2 - M1 == 0:
    print(0)
else:
    print(1)

### FIXED CODE ###

M1, D1 = map(int, input().split())
M2, D2 = map(int, input().split())

if M2 - M1 ==0:
    print(0)
else:
    print(1)
import sys
input = sys.stdin.readline
n = int(input())
xyd = [list(input().split()) for i in range(n)]
xmax,ymax = [-10**18,-10**18,-10**18],[-10**18,-10**18,-10**18]
xmin,ymin = [10**18,10**18,10**18],[10**18,10**18,10**18]
#xmax: max(x1-t,x2,x3+t)
#xmin: min(x1+t,x2,x3-t)
#ymax: max(y1-t,y2,y3+t)
#ymin: min(y1+t,y2,y3-t)
def chp(ls,a,flg1,i):
  if flg1:
    ls[i] = max(ls[i],a)
  else:
    ls[i] = min(ls[i],a)
def area(t):
  x = max(xmax[0]-t,xmax[1],xmax[2]+t)-min(xmin[0]+t,xmin[1],xmin[2]-t)
  y = max(ymax[0]-t,ymax[1],ymax[2]+t)-min(ymin[0]+t,ymin[1],ymin[2]-t)
  return x*y
for x,y,d in xyd:
  x,y = int(x),int(y)
  if d in ("L","R"):
    chp(ymax,y,1,1)
    chp(ymin,y,0,1)
    if d == "R":
      chp(xmin,x,0,0)
      chp(xmax,x,1,2)
    if d == "L":
      chp(xmin,x,0,2)
      chp(xmax,x,1,0)
  elif d in ("U","D"):
    chp(xmax,x,1,1)
    chp(xmin,x,0,1)
    if d == "U":
      chp(ymax,y,1,2)
      chp(ymin,y,0,0)
    if d == "D":
      chp(ymin,y,0,2)
      chp(ymax,y,1,0)
l = 0
r = 10**15
for _ in range(10000):
  ml = l*2/3+r*1/3
  mr = l*1/3+r*2/3
  if area(ml) <= area(mr):
    r = mr
  else:
    l = ml
print(int(area(ml)*2+0.5)/2)

### FIXED CODE ###

a,b=map(int,input().split())
if a>=b:
  print(10)
else:
  print(0)
mport sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
s = input()
index = [i for i in range(len(s)) if s[i:i+2]=="AC"]
for i in range(q):
    l, r = na()
    print(len([i for i in index if l - 1 <= i <= r - 1 and l - 1 <= i + 1 <= r - 1]))

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
s = input()
ct = [0] * n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        ct[i+1] = 1
for i in range(n-1):
    ct[i+1] += ct[i]
for i in range(q):
    l, r = na()
    l -= 1
    r -= 1
    print(ct[r] - ct[l])
import sys
from collections import deque
def m():
 s=sys.stdin.readlines()
 q=int(s[0].split()[1])
 f=lambda x,y:(x,int(y))
 d=deque(map(*e.split())for e in s[1:])
 t,a=0,[]
 while d:
  k,v=d.popleft()
  if v>q:v-=q;t+=q;d.append([k,v])
  else:t+=v;a+=[f'{k} {t}']
 print('\n'.join(a))
if'__main__'==__name__:m()


### FIXED CODE ###

import sys
from collections import deque
def m():
 s=sys.stdin.readlines()
 q=int(s[0].split()[1])
 f=lambda x,y:(x,int(y))
 d=deque(f(*e.split())for e in s[1:])
 t,a=0,[]
 while d:
  k,v=d.popleft()
  if v>q:v-=q;t+=q;d.append([k,v])
  else:t+=v;a+=[f'{k} {t}']
 print('\n'.join(a))
if'__main__'==__name__:m()
import networkx

N, M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(M)]

graph = networkx.DiGraph(edges)
SCC = list(networkx.algorithms.components.strongly_connected_components_recursive(graph))
print(len(SCC))
for comp in SCC:
    print(len(comp), *comp)


### FIXED CODE ###

import io
import os


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
N, M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(M)]

from collections import defaultdict

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v]

# https://atcoder.jp/contests/practice2/submissions/16566401
def scc(G):
    preorder = {}
    lowlink = {}
    seen = [False] * N
    scc_queue = []
    i = 0  # Preorder counter
    ans = []
    for source in range(N):
        if seen[source]:
            continue
        queue = [source]
        while queue:
            v = queue[-1]
            if v not in preorder:
                i = i + 1
                preorder[v] = i
            done = True
            for w in G[v]:
                if w not in preorder:
                    queue.append(w)
                    done = False
                    break
            if done:
                lowlink[v] = preorder[v]
                for w in G[v]:
                    if seen[w]:
                        continue
                    if preorder[w] > preorder[v]:
                        lowlink[v] = min([lowlink[v], lowlink[w]])
                    else:
                        lowlink[v] = min([lowlink[v], preorder[w]])
                queue.pop()
                if lowlink[v] == preorder[v]:
                    scc = {v}
                    seen[v] = True
                    while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
                        k = scc_queue.pop()
                        scc.add(k)
                        seen[k] = True
                    ans.append(scc)
                else:
                    scc_queue.append(v)
    return ans


SCC = list(scc(graph))

DEBUG = False
print(len(SCC))
if DEBUG:
    seen = set()
for comp in reversed(SCC):
    print(len(comp), *comp)
    if DEBUG:
        for u in comp:
            for v in graph[u]:
                assert v not in seen
        seen.update(comp)
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
min_in = A.index(1)

left = len(A[0:min_in])

right = len(A[min_in+1:])
#print(left,  right)
if N ==K:
    ans = 1
    
else:
    if (min(left, right) + 1) < K:
        ans += 1
        tuyoi = len(A-K)
        
        ans += tuyoi//K
        
        if tuyoi % K !=0:
            ans +=1
    
    else:
        if left != 0:
            ans += left//(K-1)
            
            if left%(K-1) != 0:
                ans += 1
        
        if right != 0:
            ans += right//(K-1)
            
            if right%(K-1) != 0:
                ans += 1
print(ans)

### FIXED CODE ###

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

if (N-1)%(K-1) ==0:
    print((N-1)//(K-1))
else:
    print((N-1)//(K-1)+1)
def SieveOfEratosthenes(n): 
    prime = [True for i in range(10**5 + 1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * 2, 10**5 + 1, p): 
                if prime[i]:
                    prime[i] = False
        p += 1
    prime[0], prime[1]= False, False
    count = 1
    while(True):
        if prime[p] and p>n:
            print(p)
            break
        p += 1
            
x = int(input())
SieveOfEratosthenes(n)

### FIXED CODE ###

def SieveOfEratosthenes(n): 
    prime = [True for i in range(10**6 + 1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * 2, 10**6 + 1, p): 
                if prime[i]:    prime[i] = False
        p += 1
    prime[0], prime[1] = False, False
    count = 1
    while(True):
        if prime[p] and p>=n:
            print(p);    break
        p += 1
            
n = int(input())
SieveOfEratosthenes(n)