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

#coding:utf-8
import sys
N,M=map(int,raw_input().split())
A=[-1]*(3*(10**5))
p=0
A=map(int,raw_input().split())
Q=[]
for i in range(M):
    b,c=map(int,sys.stdin.readline().split())
    Q.append((c,b))
Q.sort();Q.reverse();    
A.sort()
A.reverse()        

for c,b in Q:
    if A[-1] < c:
        A+=[c]*b
        A.sort(); A.reverse()
        A=A[:N]
print(sum(A[:N]))

### FIXED CODE ###

#coding:utf-8
import sys
N,M=map(int,raw_input().split())
A=map(int,raw_input().split())
p=0
Q=[]
for a in A: Q.append((a,1))
for i in range(M):
    b,c=map(int,sys.stdin.readline().split())
    Q.append((c,b))
Q.sort();Q.reverse()
n=0;s=0
for c,b in Q:
    if b+n<=N:
        s+=c*b
        n+=b
    else:
        s+=c*(N-n)
        break
print(s)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
a.sort()
n = 0
for i in range(N):
  d = True
  for j in range(N):
    if a[i] < a[j]:
      break
    elif i != j and a[i] % a[j] == 0:
      d = False
      break
  if d:
    n += 1
print(n)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
a.sort()
A = max(a)
b = [0]*A
for i in range(N):
  if b[a[i]-1] == 0:
    for j in range(a[i], A+1, a[i]):
      b[j-1] += 1
  elif b[a[i]-1] == 1:
      b[a[i]-1] += 1
n = 0      
for i in range(N):
  if b[a[i]-1] == 1:
    n += 1
print(n)
### BUGGY CODE ###


N,Ma,Mb = map(int,input().split())

lis = [[float("inf")] * 401 for i in range(401)]
lis[0][0] = 0

for x in range(N):

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

    olis = []
    for i in lis:
        olis.append(i.copy())

    for i in range(401):

        for j in range(401):

            if olis[i][j] != float("inf"):

                if i + a < 400 and j + b < 400:

                    lis[i+a][j+b] = min( olis[i][j] + c , lis[i+a][j+b] )

ans = float("inf")

for i in range(400):

    i += 1

    for j in range(400):

        j += 1

        if i * Mb == j * Ma:

            ans = min(ans , lis[i][j])

if ans == float("inf"):
    print (-1)
else:
    print (ans)

### FIXED CODE ###


N,Ma,Mb = map(int,input().split())

lis = [[float("inf")] * 401 for i in range(401)]
lis[0][0] = 0

for x in range(N):

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

    olis = []
    for i in lis:
        new = []
        for j in i:
            new.append(j)
        olis.append(new)

    for i in range(401):

        for j in range(401):

            if olis[i][j] != float("inf"):

                if i + a < 400 and j + b < 400:

                    lis[i+a][j+b] = min( olis[i][j] + c , lis[i+a][j+b] )

ans = float("inf")

for i in range(400):

    i += 1

    for j in range(400):

        j += 1

        if i * Mb == j * Ma:

            ans = min(ans , lis[i][j])

if ans == float("inf"):
    print (-1)
else:
    print (ans)
### BUGGY CODE ###

n = int(input())
a_list = [int(input()) for _ in range(n)]
for i in range(len(a_list)):
    print(max(a_list[:i]+a_list[i+1:]))

### FIXED CODE ###

import heapq
n = int(input())
a_list = [int(input()) for _ in range(n)]
a_list_heap = list(map(lambda x:(-1)*x,a_list))
heapq.heapify(a_list_heap)
max_num = a_list_heap[0]*(-1)

for i in range(len(a_list)):
    if a_list[i] != max_num:
        print(max_num)
    else:
        tmp = heapq.heappop(a_list_heap)
        print(a_list_heap[0]*(-1))
        heapq.heappush(a_list_heap,tmp)
### BUGGY CODE ###


d=[0]*13
d[0]=1
mul=1
t=reversed(input())
for c in t:
    e=[0]*13
    """
    if c=="?":
        for i in range(10):
            for j in range(13):
                e[(i*mul+j)%13]+=d[j]
                e[(i*mul+j)%13]%=(10**9+7)
    else:
        for j in range(13):
            e[(int(c)*mul+j)%13]+=d[j]
            e[(int(c)*mul+j)%13]%=(10**9+7)
    """
    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            e[(i*mul+j)%13]+=d[j]
            
    d=[e%(10**9+7)for e in e]
    mul*=10
print(d[5])



### FIXED CODE ###

# coding: utf-8
# Your code here!
 
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意
 
s = input()
l = len(s)
MOD = 10**9+7
 
dp = [0]*13
dp[0] = 1
for i in s:
    new = [0]*13
    if i == "?":
        for i in range(10):
            for j in range(13):
                new[(10*j+i)%13] += dp[j]
    else:
        i = int(i)
        for j in range(13):
            new[(i+10*j)%13] += dp[j]
    
    for i in range(13):
        new[i] %= MOD
    dp,new = new,dp
#    print(dp)
 
print(dp[5]%MOD)
### BUGGY CODE ###

from collections import deque
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

F = [[[] for _ in range(2)] for _ in range(N)]
for m in AB:
    F[m[0] - 1][0].append(m[1] - 1)
    F[m[1] - 1][0].append(m[0] - 1)
for k in CD:
    F[k[0] - 1][1].append(k[1] - 1)
    F[k[1] - 1][1].append(k[0] - 1)

for i in range(N):
    c = 0
    d = [0] * N
    d[i] = 1
    Q = deque()
    Q.append(i)
    while len(Q) > 0:
        q = Q.pop()
        for j in range(len(F[q][0])):
            a = F[q][0][j]
            if d[a] == 1:
                continue
            d[a] = 1
            c += 1
            Q.append(a)
    for j in range(len(F[i][1])):
        a = F[i][1][j]
        if d[a] == 1:
            c -= 1            
    print(c -len(F[i][0]), end=' ')

print('')

### FIXED CODE ###

import time
from collections import deque
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

F = [set() for _ in range(N)]
B = [set() for _ in range(N)]

for i, j in AB:
    F[i - 1].add(j - 1)
    F[j - 1].add(i - 1)
for i, j in CD:
    B[i - 1].add(j - 1)
    B[j - 1].add(i - 1)

Q = deque()
S = [0] * N
d = [0] * N

for i in range(N):
    if d[i] != 0:
        continue
    L = {i}
    d[i] = 1
    Q.append(i)
    while len(Q) > 0:
        q = Q.pop()
        for j in F[q]:
            if d[j] == 0:
                d[j] = 1
                Q.append(j)
                L.add(j)
    for k in L:
        S[k] = len(L) - len(L & F[k]) - len(L & B[k]) - 1

print(*S)
### BUGGY CODE ###

n = int(input())

for i in range(1, n+1):
    cnt = 0
    j = int(i**0.5)

    for x in reversed(range(1, j)):
        for y in reversed(range(1, x+1)):
            for z in reversed(range(1, y+1)):
                if i == x**2 + y**2 + z**2 + x*y + y*z + z*x:
                    if x==y==z:
                        cnt += 1
                    elif x==y or y==z or z==x:
                        cnt += 3
                    else:
                        cnt += 6
                    break

    print(cnt)


### FIXED CODE ###

n = int(input())
num = [0]*10000

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            a = x**2 + y**2 + z**2 + x*y + y*z + z*x - 1
            if a <= 9999:
                num[a] += 1

num = num[:n]

for i in num:
    print(i)
### BUGGY CODE ###

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

a = [input().split() for i in range(m)]
c = []
d = []
for i in range(m):
    if int(a[i][0]) == 1 and int(a[i][1]) == n:
        continue
    elif int(a[i][0]) == 1:
        c.append(int(a[i][1]))
    elif int(a[i][1]) == n:
        d.append(int(a[i][0]))
ans = False
c = list(set(c))
for i in c:
    if d.count(i) >=1:
        ans = True
        break
if ans:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

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

for i in range(m):
    a[i],b[i] = map(int,input().split())

go = []
goal = []

for i in range(len(a)):
    if a[i] == 1:
        go.append(b[i])
    if b[i] == n:
        goal.append(a[i])

count = [0 for i in range(n)]
for i in range(len(go)):
    count[go[i]-1] = 1
for i in range(len(goal)):
    count[goal[i]-1] += 1
for i in range(len(count)):
    if count[i] > 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

import bisect
N, M = map(int, input().split())
P, Y = [], []
pref = [[] for _ in range(N+1)] # non-0-indexed
for m in range(M):
    p,y = map(int, input().split())
    P.append(p)
    Y.append(y)
    bisect.insort(pref[p], y)

    
for p,y in zip(P,Y):
    ans = "{:0>6}".format(p)
    i = bisect.bisect(pref[p], y)
    ans += "{:0>6}".format(i)
    print(ans)

### FIXED CODE ###

import bisect
N, M = map(int, input().split())
P, Y = [], []
pref = [[] for _ in range(N+1)] # non-0-indexed
for m in range(M):
    p,y = map(int, input().split())
    P.append(p)
    Y.append(y)
    pref[p].append(y)

for i,pre in enumerate(pref):
    pref[i] = sorted(pre)

for p,y in zip(P,Y):
    a = "{:0>6}".format(p)
    i = bisect.bisect(pref[p], y)
    a += "{:0>6}".format(i)
    print(a)
### BUGGY CODE ###

import math
A, B, N = [int(n) for n in input().split()]

max = 0
for x in range(N+1):
    val = A * ((x / B) % 1) - ((A*x/B) % 1)
    # val = math.floor(A*x/B) - A*math.floor(x/B)
    if val > max:
        max = val
print(int(max))

### FIXED CODE ###

A, B, N = [int(n) for n in input().split()]

print(int(A*min(N,B-1)/B))
### BUGGY CODE ###

N,M=map(int, input().split())
f=[]
for i in range(M):
    a,b = map(int, input().split())
    for i in f:
        if a in i or b in i:
            i.add(a)
            i.add(b)
            break
    else:
        f.append(set((a,b)))

x = 0
for i in f:
    x=max(x,len(i))
if M == 0:
    x = 1
print(x)


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

N,M=map(int, input().split())
mx=0
uf = UnionFind(N+1)
for i in range(M):
	a,b = map(int, input().split())
	uf.union(a,b)
for i in uf.parents:
	mx = max(mx, uf.size(i))
if M == 0:
	mx = 1
print(mx)
### BUGGY CODE ###

n,m = map(int,input().split())
edge = [0] * (n-1)
for i in range(m):
    a,b = map(int,input().split())
    if a > b:
        a,b = b,a
    for j in range(a,b):
        edge[j-1] += 1
for i in range(len(edge)):
    if edge[i] % 2 == 1:
        print("NO")
        exit()
print("YES")




### FIXED CODE ###

n,m = map(int,input().split())
point = [0] * n
cnt = 0
for i in range(m):
    a,b = map(int,input().split())
    point[a-1] += 1
    point[b-1] += 1
    # if a > b:
    #     a,b = b,a
    # for j in range(a,b):
    #     edge[j-1] += 1
for i in range(len(point)):
    if point[i] % 2 == 1:
        print("NO")
        exit()
print("YES")
### BUGGY CODE ###

N, Q = map(int, input().split())
A = list(map(int, input().split()))
MAX_A = 5 * 10 ** 5
query = []
for q in range(Q):
    l, r = map(int, input().split())
    query.append((l, r, q))


# 一番後ろの1を削りながら0までやるイメージ
# 1-indexed
# 閉区間
# 区間[s, t]の和 => BIT.add(t) - BIT.add(s - 1)

class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [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):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N)
X = [-1] * (MAX_A + 1)
for i, a in enumerate(A, start=1):
    X[a] = i
for x in X:
    if x == -1:
        continue
    BIT.add(x, 1)

ans = [-1] * Q
query.sort(key=lambda x: x[1])

for l, r, i in query:
    BIT.add(X[A[r - 1]], -1)
    X[A[r - 1]] = r
    BIT.add(r, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print(*ans, sep='\n')


### FIXED CODE ###

def main():
    import sys
    my_input = sys.stdin.readline
    N, Q = map(int, my_input().split())
    A = list(map(int, my_input().split()))

    MAX_A = 5 * 10 ** 5
    query = []
    for q in range(Q):
        l, r = map(int, my_input().split())
        query.append((l, r, q))

    class BinaryIndexedTree:
        def __init__(self, n):
            self.size = n
            self.bit = [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):
            while i <= self.size:
                self.bit[i] += x
                i += (i & -i)

        def reset(self):
            self.bit = [0] * (self.size + 1)


    BIT = BinaryIndexedTree(N)
    X = [-1] * (MAX_A + 1)
    for i, a in enumerate(A, start=1):
        X[a] = i
    for x in X:
        if x == -1:
            continue
        BIT.add(x, 1)

    ans = [-1] * Q
    query.sort(key=lambda x: x[1])

    mr = 0
    for l, r, i in query:
        while mr < r:
            mr += 1
            BIT.add(X[A[mr - 1]], -1)
            X[A[mr - 1]] = mr
            BIT.add(mr, 1)
        ans[i] = BIT.sum(r) - BIT.sum(l - 1)

    for a in ans:
        print(a)


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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from pprint import pprint as pp
from pprint import pformat as pf

import math

def calc(a, b, x):
    return math.floor(a * x / b) - a * math.floor(x / b)

if __name__ == '__main__':
    a, b, n = map(int, input().split())
    if b > n:
        x = n
        m = calc(a, b, x)
    else:
        m = 0
        k = 1
        while b * k <= n:
            v = calc(a, b, b * k - 1)
            m = max(m, v)
            k += 1
    print(m)


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from pprint import pprint as pp
from pprint import pformat as pf

import math

def calc(a, b, x):
    return math.floor(a * x / b) - a * math.floor(x / b)

if __name__ == '__main__':
    a, b, n = map(int, input().split())
    if b > n:
        m = calc(a, b, n)
    else:
        m = calc(a, b, b - 1)
    print(m)
### BUGGY CODE ###

h,w = map(int,input().split())
al = []
for _ in range(h):
    a = list(map(int,input().split()))
    al.append(a)

bl = []
for _ in range(h):
    b = list(map(int,input().split()))
    bl.append(b)

abl = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        abl[i][j] = al[i][j] - bl[i][j]

from collections import defaultdict
dic = [[[0 for i in range(12801)] for _ in range(w)] for _ in range(h)]

dic[0][0][abl[i][j] + 6400] = 1
dic[0][0][-abl[i][j]+ 6400] = 1

for i in range(h):
    for j in range(w):
        for v, t in enumerate(dic[i][j]):
            if t == 1:
                if j + 1 < w:
                    if 0 <= v+abl[i][j+1] <= 12800:
                        dic[i][j+1][v+abl[i][j+1]] = 1
                    if 0 <= v-abl[i][j+1] <= 12800:
                        dic[i][j+1][v-abl[i][j+1]] = 1
                if i + 1 < h:
                    if 0 <=v+abl[i+1][j] <= 12800:
                        dic[i+1][j][v+abl[i+1][j]] = 1
                    if 0 <= v-abl[i+1][j] <= 12800:
                        dic[i+1][j][v-abl[i+1][j]] = 1

ans = float("inf")
for idx,i in enumerate(dic[-1][-1]):
    if i == 1:
        ans = min(ans, abs(idx-6401))
print(ans)




### FIXED CODE ###

h,w = map(int,input().split())

bitdp = [[0 for j in range(w)] for i in range(h)]
al = []
bl = []
for _ in range(h):
   a = list(map(int,input().split()))
   al.append(a)
for _ in range(h):
   b = list(map(int,input().split()))
   bl.append(b)
abl = [[] for i in range(h)]
for i in range(h):
   for j in range(w):
      abl[i].append(abs(al[i][j] - bl[i][j]))

bitdp[0][0] = 1 << h*w+abl[0][0]
for i in range(h):
   for j in range(w):
      if j != w-1:
         bitdp[i][j+1] |= bitdp[i][j] << abl[i][j+1] | bitdp[i][j] >> abl[i][j+1]
      if i != h-1:
         bitdp[i+1][j] |= bitdp[i][j] << abl[i+1][j] | bitdp[i][j] >> abl[i+1][j]

ans = []
for i in range(h*w*2+1):
   if (bitdp[-1][-1] >> i & 1):
      ans.append(abs(h*w-i))

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

n = int(input())
a = list(input())

r = 0
for i in range(1000):
  t = str(i).zfill(3)
  ti = 0
  for si in range(n):
    if a[si] == t[ti]:
      ti += 1
      if ti == 3:
        break
  if ti == 3:
    r += 1
print(r)
  

### FIXED CODE ###

n = int(input())
a = input()

r = 0
for i in range(10):
  s = a.find(str(i))
  if s == -1:
    continue
  for j in range(10):
    s2 = a.find(str(j), s + 1)
    if s2 == -1:
      continue
    for k in range(10):
      if a.find(str(k), s2 + 1) != -1:
        r += 1
print(r)
### BUGGY CODE ###

N = map(int,input())
A = list(map(int,input().split()))
dup = [i for i in set(A) if A.count(i) > 1]
print("NO" if dup else "YES")

### FIXED CODE ###

def has_duplicates(seq):
    return len(seq) != len(set(seq))
    
N = map(int,input())
A = list(map(int,input().split()))
print("NO" if has_duplicates(A) else "YES")
### BUGGY CODE ###

INF = 10 ** 11
BLACK = '#'
H, W = [int(i) for i in input().split()]
M = [None] * H
D = [[INF] * W for _ in range(H)]

for i in range(H):
    inputs = input()
    for idx, j in enumerate(inputs):
        if j == BLACK:
            D[i][idx] = 0


def forward_update(i, j):
    up = INF
    if i > 0:
        up = D[i-1][j]
    left = INF
    if j > 0:
        left = D[i][j-1]

    D[i][j] = min(D[i][j], up + 1, left + 1)


def backward_update(i, j):
    down = INF
    if i < H-1:
        down = D[i+1][j]
    right = INF
    if j < W-1:
        right = D[i][j+1]
    D[i][j] = min(D[i][j], down + 1, right + 1)


_ = [forward_update(i, j) for i in range(H) for j in range(W)]
_ = [backward_update(i, j) for i in range(H-1, -1, -1) for j in range(W-1, -1, -1)]

max_value = max([max(x) for x in D])
print(max_value)


### FIXED CODE ###

INF = 10 ** 11
BLACK = '#'
H, W = [int(i) for i in input().split()]
M = [None] * H
D = [[INF] * W for _ in range(H)]

for i in range(H):
    inputs = input()
    for idx, j in enumerate(inputs):
        if j == BLACK:
            D[i][idx] = 0


def forward_update(i, j):
    up = INF
    if i > 0:
        up = D[i-1][j]
    left = INF
    if j > 0:
        left = D[i][j-1]

    D[i][j] = min(D[i][j], up + 1, left + 1)


def backward_update(i, j):
    down = INF
    if i < H-1:
        down = D[i+1][j]
    right = INF
    if j < W-1:
        right = D[i][j+1]
    D[i][j] = min(D[i][j], down + 1, right + 1)


_ = [forward_update(i, j) for i in range(H) for j in range(W)]
_ = [backward_update(i, j) for i in range(H-1, -1, -1) for j in range(W-1, -1, -1)]

max_value = max([max(x) for x in D])
print(max_value)
### BUGGY CODE ###

N = int(input())

a = list(map(int, input().split()))
ans = 1
for i in range(N):
    ans = ans * a[i]
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

N = int(input())

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

n = int(input())
x = [int(i) for i in input().split()]
sortedx = sorted(x)
dict = {k:sortedx[:i]+sortedx[i+1:] for i,k in enumerate(sortedx)}
med = (n-1)//2
for i in x:
    print(dict[i][med])


### FIXED CODE ###

n = int(input())
X = [int(i) for i in input().split()]
sX = sorted(X)
r,l = sX[n//2],sX[n//2-1]
if r != l:
    for x in X:
        if x<=l: print(r)
        else: print(l)
else:
    for _ in range(n): print(l)
### BUGGY CODE ###

from collections import defaultdict


n, k = map(int, input().split())
children = defaultdict(list)
children[1].append(0)
for i in range(n-1):
  parent, child = map(int, input().split())
  children[parent].append(child)
  children[child].append(parent)
  
def cal(x, k):
  patt = k-2
  if x == 1:
    patt += 1
  res = 1
  child = len(children[x])-1
  for i in range(child):
    res *= patt
    patt -= 1
  
  return res

ans = k
for i in range(1, n+1):
  res = cal(i, k)
  ans *= res
  ans %= 1000000007

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
mod = 10**9 + 7


def perm(n, k):
    if k == 0:
        return 1
    return n * perm(n-1, k-1) % mod


n, k = map(int, input().split())
child = [0] * n

for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    child[a] += 1
    child[b] += 1

ans = k
for i in range(n):
    if i == 0:
        color = k - 1
        num = child[i]
    else:
        color = k - 2
        num = child[i] - 1
    ans = ans * perm(color, num) % mod

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

def is_same(x, y, z, s):
    return x+y+z == s


k, s = [int(e) for e in input().split()]
ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if is_same(x,y,z,s):
                ans += 1
print(ans)

### FIXED CODE ###

k, s = [int(e) for e in input().split()]
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z and z <= k:
            ans = ans + 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
minIndex = [i for i, x in enumerate(A) if x == min(A)]
print((minIndex[0]+1)//K+(len(A)-max(minIndex[0], 1))//K+1)


### FIXED CODE ###

import math
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
minIndex = A.index(min(A))
if K == len(A):
    print(1)
else:
    print(math.ceil((N-1)/(K-1)))
### BUGGY CODE ###

count = int(input())
numbers = map(int, input().split(' '))

tmp = 0
counter = 0
while True:
  for item in numbers:
    tmp += item % 2
  if tmp > 0:
    break
  counter += 1
  numbers = [item / 2 for item in numbers]

print(counter)

### FIXED CODE ###

count = int(input())
numbers = [int(num) for num in input().split()]

counter = 0
while True:
  tmp = 0
  for item in numbers:
    tmp += item % 2
  if tmp > 0:
    break
  counter += 1
  numbers = [item / 2 for item in numbers]
print(counter)
### BUGGY CODE ###

import numpy as np
import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


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

    def lcm(x, y):
        return x * y // fractions.gcd(x, y)
        
    
    x = functools.reduce(lcm, A, 1)
        
    b = sum(x//a for a in A)
    print(b%MOD)
if __name__== "__main__":
    main()


### FIXED CODE ###

import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


def main():
    # N = int(input())
    # A = list(map(int, input().split()))
    N, *A = map(int, open(0).read().split())
            
    x = 1
    for a in A:
        x *= a //  fractions.gcd(x, a)
        
    b = sum(x//a for a in A)
    print(b%MOD)
    
if __name__== "__main__":
    main()
### BUGGY CODE ###

import fractions
from functools import reduce
import random
import copy

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

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

if n < 10000:
  for i in range(n):
    b = copy.copy(a)
    b.pop(i)
    t = gcd(b)
    if ans < t:
      ans = t
else:
  for _ in range(200):
    t = gcd(random.sample(a, 50))
    if ans < t:
      ans = t

print(ans)

### FIXED CODE ###

import fractions
from functools import reduce
import random
import copy

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

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

if n < 1000:
  for i in range(n):
    b = copy.copy(a)
    b.pop(i)
    t = gcd(b)
    if ans < t:
      ans = t
else:
  for _ in range(200):
    t = gcd(random.sample(a, 500))
    if ans < t:
      ans = t

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

import fractions
N=int(input())
A=list(map(int,input().split()))
L=[0]
R=[0]
ans=1
for i in range(N):
    if i==N-1:
        pass
    else:
        R.append(fractions.gcd(R[-1], A[::-1][i]))
        L.append(fractions.gcd(L[-1], A[i]))
print(max(fractions.gcd(l,r)for l,r in zip(L,R[::-1])))

### FIXED CODE ###

from  fractions import gcd
N=int(input())
A=list(map(int,input().split()))
L=[0]
R=[0]
ans=1
for i in range(N-1):
    R.append(gcd(R[-1], A[-1-i]))
    L.append(gcd(L[-1], A[i]))
print(max(gcd(l,r)for l,r in zip(L,R[::-1])))