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

from collections import deque

def merge(A,B):
    ans = deque()
    count = 0
    while(True):
        if len(A)==0 and len(B) == 0:
            break
        elif len(A) == 0:
            ans.append(B.popleft())
        elif len(B) == 0:
            ans.append(A.popleft())
        elif A[0] > B[0]:
            ans.append(B.popleft())
        else:
            ans.append(A.popleft())
        count+=1
    return (ans.copy(),count)

n = int(input())
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.pop()
    if(len(d)>2):
        mid = len(d)//2
        div.appendleft(d[:mid])
        div.appendleft(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            d.reverse()
        mer.appendleft(d)
        count+=2
    else:
        mer.appendleft(d)
        
while(len(mer)>1):
    A = deque(mer.popleft())
    B = deque(mer.popleft())
    ret = merge(A,B)
    mer.append(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print(ans[:-1])
print(count)


### FIXED CODE ###

from collections import deque

def merge(A,B):
    ans = [0]*(len(A)+len(B))
    count=i=j=0
    A+=[10**9+1]
    B+=[10**9+1]
    for k in range(len(ans)):
        if A[i]<B[j]:
            ans[k]=A[i]
            i+=1
        else:
            ans[k]=B[j]
            j+=1
        count+=1
    return (ans,count)

n = int(input())
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.popleft()
    if(len(d)>2):
        mid = len(d)//2
        div.append(d[:mid])
        div.append(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            mer.append(d[::-1])
        else:
            mer.append(d)
        count+=2
    else:
        mer.append(d)
        
while(len(mer)>1):
    A = mer.pop()
    B = mer.pop()
    ret = merge(A,B)
    mer.appendleft(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print(ans[:-1])
print(count)
### BUGGY CODE ###

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

### FIXED CODE ###

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

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

dp = [[0]*N for i in range(N)]

for i, a in enumerate(A):
  dp[i][i] = a

for i in range(1, N):
  for j in range(i-1, -1, -1):
    dp[i][j] = max(A[i]-dp[i-1][j], A[j]-dp[i][j+1])

print(dp[N-1][0])

### FIXED CODE ###

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

dp = [[0]*N for i in range(N)]

for i, a in enumerate(A):
  dp[i][i] = a

for i in range(1, N):
  for j in range(i-1, -1, -1):
    dp[i][j] = max(A[i]-dp[i-1][j], A[j]-dp[i][j+1])

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

import sys
input = sys.stdin.readline

n = int(input())
a = [int(i) for i in input().split()]
b = sorted(a)

l = [a.index(i)+1 for i in b]

  
print(*l)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
List = [0]*N
 
 
for i, a in enumerate(A):
  List[int(a)-1] = str(i+1)
 
  
print(" ".join(List))
### BUGGY CODE ###

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

A_set = set(A)

def cmb2(n):
	result = n * (n - 1) / 2

	return int(result)

ans_d = {}
for a_s in A_set:
	#print(A.count(a))
	ans_d[str(a_s)] = A.count(a_s)

for a in A:
    A_new = ans_d.copy()
    A_new[str(a)] -= 1
    ans = 0
    #print(A_new)
    #print("="*10)
    for a_n in A_new.values():
        if a_n <= 1:
            continue
        else:
            ans += cmb2(a_n)
    print(ans)

### FIXED CODE ###

import sys
from collections import Counter

def cmb2(n):
	if n < 2:
		return 0

	return n * (n-1) // 2

if __name__ == "__main__":

	N = int(input())
	A = [int(i) for i in input().split()]
	# A = list(map(int, input().split()))

	c = Counter(A)
	s = 0
	for v in c.values():
		s += cmb2(v)

	for a in A:
		print(s - cmb2(c[a]) + cmb2(c[a] - 1))
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC74 C

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

s = f//(100*a)
t = f//(100*b)
u = f//c
v = f//d

concentration = 0
water = [100*a*A + 100*b*B for B in range(t+1) for A in range(s+1) if 100*a*A + 100*b*B != 0]
suger = [c*C + d*D for D in range(v+1) for C in range(u+1)]
ans1 = 0
ans2 = 0
for W in water:
    for S in suger:
        if W + S <= f:
            if W//100*e >= S:
                if concentration < S/(W+S):
                    concentration = S/(W+S)
                    ans1 = W+S
                    ans2 = S
if ans1 == 0:
    ans1 = 100*a
print(ans1,ans2)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC74 C

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

s = f//(100*a)
t = f//(100*b)
u = f//c
v = f//d

concentration = 0
solution = 0
suger = 0
for A in range(s+1):
    for B in range(t+1):
        for C in range(u+1):
            for D in range(v+1):
                if 100*a*A + 100*b*B + c*C + d*D <= f:
                    if (a*A+b*B)*e >= (c*C + d*D):
                        if 100*a*A + 100*b*B + c*C + d*D != 0:
                            if concentration < (c*C + d*D)/(100*a*A + 100*b*B + c*C + d*D):
                                concentration = (c*C + d*D)/(100*a*A + 100*b*B + c*C + d*D)
                                solution = 100*a*A + 100*b*B + c*C + d*D
                                suger = c*C + d*D
if solution == 0:
    solution = 100*a
print(solution,suger)
### BUGGY CODE ###

#inport
import sys
import numpy as np

#input
N,M = map(int, sys.stdin.readline().split())
P = [list(map(int, sys.stdin.readline().split())) for i in range(M)]

#shori
##初期化
ans = np.zeros((N,3))
tmp_latest = np.zeros(1)
tmp_latest_tmp = np.zeros(1)
tmp_latest[0] = 1
pos_latest = 0
num_latest = 1
ans[0][1] = 1 #部屋1をてがかりありに
ans[0][2] = 1 #部屋1をてがかりありに
flg_pos = 1
flg_fale = 0
num_crew = 0

for i in range(N):
    ans[i][0] = i + 1

while num_crew < N:
    if flg_pos == 0:
        flg_fale = 1
        break

    flg_pos = 0
    for i in range(N):
        if ans[i][2] == 0:
            #手がかりが置いてなければ置ける手がかりを探索
            tmp_room_num = ans[i][0]

            for j in range(M):
                if P[j][1] == tmp_room_num:
                    if P[j][0] in tmp_latest:
                        ans[P[j][1]-1][1] = P[j][0]
                        ans[P[j][1]-1][2] = 1
                        tmp_latest_tmp = np.insert(tmp_latest_tmp, 0, tmp_room_num)
                        flg_pos = 1
                        break
                elif P[j][0] == tmp_room_num: 
                    if P[j][1] in tmp_latest:
                        ans[P[j][0]-1][1] = P[j][1]
                        ans[P[j][0]-1][2] = 1
                        tmp_latest_tmp = np.insert(tmp_latest_tmp, 0, tmp_room_num)
                        flg_pos = 1
                        break

    #Nループ終了時にtmp_latestを更新
    tmp_latest = np.insert(tmp_latest, num_latest, tmp_latest_tmp)
    for j in range(num_latest):
        tmp_latest = np.delete(tmp_latest,0)
    
    num_latest = np.size(tmp_latest)
    num_crew = np.sum(ans,axis = 0)[2]

if flg_fale == 0:
    print('Yes')
    for i in range(N-1):
        print(int(ans[i+1][1]))
else:
    print('No')


### FIXED CODE ###

#inport
import sys
import numpy as np
from collections import deque


#input
N,M = [int(x) for x in sys.stdin.readline().split()]
g = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = [int(x) for x in sys.stdin.readline().split()]
    g[a].append(b)
    g[b].append(a)



quetmp = deque([1])
d = [None] * (N+1)
d[1] = 0
num_crew = 1
while quetmp:
    v = quetmp.popleft()
    for i in g[v]:
        if d[i] is None:
            d[i] = v
            quetmp.append(i)
            num_crew = num_crew + 1

if num_crew == N:
    print('Yes')
    for i in range(N-1):
        print(d[i+2])
else:
    print('No')
### BUGGY CODE ###

N = int(input())
output = 0
for i in range(1,N):
    output += i
print(output)

### FIXED CODE ###

N = int(input())
output = int(N*(N-1)//2)
print(output)
### BUGGY CODE ###

s=input()
t=list(s)
u=sorted(list(set(t)))
ans=[]
for i in range(min(5,len(u))):
  ans.append(u[i])
k=int(input())
for j in range(1,min(5,len(t))):
  c=[]
  for i in range(len(t)-j):
    c.append(s[i:i+j+1])
    c=sorted(list(set(c)))
  for l in range(min(5,len(c))):
    ans.append(c[l])
ans=sorted(ans)
print(ans[k-1])


### FIXED CODE ###

s=input()
t=list(s)
u=sorted(list(set(t)))
ans=[]
for i in range(len(u)):
  ans.append(u[i])
k=int(input())
for j in range(1,min(10,len(t))):
  for i in range(len(t)-j):
    ans.append(s[i:i+j+1])
ans=sorted(list(set(ans)))
print(ans[k-1])
### BUGGY CODE ###

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

cnt = 0
ans = 0
while cnt < M:
    min_cost = min(A)
    min_index = A.index(min_cost)
    amount = B[min_index]
    if cnt + amount <= M:
        ans += min_cost * amount
        cnt += amount
    else:
        ans += min_cost * (M - cnt)
        break
    A = [A[i] for i in range(len(A) - 1) if i != min_index]
    B = [B[i] for i in range(len(B) - 1) if i != min_index]
    
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
AB = [0] * N
for i in range(N):
    AB[i] = list(map(int, input().split()))

AB = sorted(AB)
cnt = 0
ans = 0

for e in AB:
    if cnt + e[1] < M:
        ans += e[0] * e[1]
        cnt += e[1]
    else:
        ans += e[0] * (M - cnt) 
        break

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

n,k = map(int,input().split())
h = list(map(int, input().split()))
v = [0 for _ in range(n)]
for i in range(1,n):
	u = h[i]
	v[i] = min([v[j] + abs(h[j]-u) for j in range(max(0, i-k), i)])
print(v[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int, input().split()))
v=[0]*n
for i in range(1,n):
	u = h[i]
	v[i] = min([v[j] + abs(h[j]-u) for j in range(max(0, i-k), i)])
print(v[n-1])
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
INF = 10**10

dp = [INF]*N
dp[0] = 0

for i in range(N):
    for k in range(1,K+1):
        if i-k>=0:
            dp[i] = min(dp[i],dp[i-k]+abs(h[i]-h[i-k]))

print(dp[-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
INF = 10**10

dp = [INF]*N
dp[0] = 0

for i,hi in enumerate(h):
    if i == 0:
        continue
    s = i-K if i-K >= 0 else 0
    dp[i] = min([dpk + abs(hi-hk) for dpk,hk in zip(dp[s:i],h[s:i])])

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

N=int(input())
L=list(map(int,input().split()))
 
cnt=0
for i in range(N):
    cnt= cnt + sum([(L[i+x]+L[i])==x for x in range(N-i) if (L[i+x]+L[i])<=x])
    
print(cnt)

### FIXED CODE ###

def main():
    N=int(input())
    L=list(map(int,input().split()))
    L_i,L_j=[],[]
    L_memo = [0]*N
    cnt=0
    for i, j in enumerate(L):
        if i+j<N:
            L_memo[i+j]+=1
        if i-j>0:
            cnt+=L_memo[i-j]        
    print(cnt)
main()
### BUGGY CODE ###

MOD = 10**9+7
def resolve():
    H, W = list(map(int, input().split()))
    S = [list(input()) for _ in range(H)]
    import collections
    maxdist = 0
    for startx in range(H):
        for starty in range(W):
            if S[startx][starty] == "#":
                continue
            visited = [[-1 for _ in range(W)] for __ in range(H)]
            q = collections.deque([(startx, starty, 0)])
            while q:
                x, y, dist = q.pop()
                visited[x][y] = dist
                for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != "#" and visited[nx][ny] == -1:
                        q.appendleft((nx, ny, dist+1))
            maxdist = max(maxdist,max(sum(visited, [])))
    print(maxdist)
    

if '__main__' == __name__:
    resolve()


### FIXED CODE ###

def resolve():
    H, W = list(map(int, input().split()))
    S = [list(input()) for _ in range(H)]
    import collections
    maxdist = 0

    for startx in range(H):
        for starty in range(W):
            if S[startx][starty] == "#":
                continue
            visited = [[-1 for _ in range(W)] for __ in range(H)]
            visited[startx][starty] = 0
            q = collections.deque([(startx, starty)])
            while q:
                x, y = q.pop()
                for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != "#" and visited[nx][ny] == -1:
                        visited[nx][ny] = visited[x][y] + 1
                        q.appendleft((nx, ny))
            maxdist = max(maxdist,max(sum(visited, [])))
    print(maxdist)
    

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

n = int(input())
h = list(map(int,input().split()))
c = 0
for i in range(n-1):
    count = 0
    for j in range(i,n-1):
        if h[j] >= h[j+1]:
            count += 1
        else:
            break
        if count > c:
            c = count
print(c)

### FIXED CODE ###

import sys
n = int(input())
h = list(map(int,input().split()))
result = []
c = 0
if n == 1:
    print(0)
    sys.exit()
for i in range(n-1):
    if h[i] >= h[i+1]:
        c += 1
    else:
        result.append(c)
        c = 0
    if i == n-2:
        result.append(c)

print(max(result))
### BUGGY CODE ###


N,M = map(int,input().split())

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

ans = 0

for i in range(M):
    bi,ci = map(int,input().split())
    A_list=sorted(A_list)
    for j in range(bi):
        if A_list[j] < ci:
            A_list[j] = ci
        else :
            break

print(sum(A_list))


### FIXED CODE ###


#AのリストにCのリストを加えて大きい順に並べ替えてNまでの和を求める
N,M = map(int,input().split())

#Aの入力
A_list = list(map(int,input().split()))

C_list = []

#Cのリストに追加する
for i in range(M):
    bi,ci = map(int,input().split())
    C_list.append([bi,ci])

#C_listをCの値でソート
C_list=sorted(C_list, reverse=True, key=lambda x:x[1])

count = 0
for bi,ci in C_list:
    count += bi
    if count > N:
        #countがNより大きくなったらNより大きくなった分だけ使う
        bi = N - count + bi
    A_list.extend([ci]*bi)

#A_Listを大きい順に並べ替える
A_list=sorted(A_list,reverse=True)

#N番目までの総和を求める
print(sum(A_list[0:N]))
### BUGGY CODE ###

#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections

N = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

from math import gcd

pairwise = True
setwise = True
acc = a[0]
for i in range(N):
    acc = gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

for i in range(N):
    for j in range(i+1,N):
        b = gcd(a[i],a[j])
        if b != 1:
            print("setwise coprime")
            exit()
if pairwise == True:
    print("pairwise coprime")
# elif setwise == True:
#     print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

import math
from collections import defaultdict
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
class Sieve_of_Eratosthenes:
    def __init__(self, N):
        self.sieve = [-1] * (N+1)
 
        for i in range(2,N+1):
            if self.sieve[i] == -1:
                for j in range(1,1+N//i):
                    self.sieve[i*j] = i
 
    def isprime(self, num):
        if num <= 1:
            return False
        else:
            return self.sieve[num] == num
 
    def factorization(self, num):
        ret = set([])
        while num != 1:
            div = self.sieve[num]
            ret.add(div)
            num //= div
        return ret
 
sofe = Sieve_of_Eratosthenes(M)
ddic = defaultdict()
judge = set([])
 
for i in a:
    if not pc:
        break
    asf = sofe.factorization(i)
    
    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

Mod = 10**9+7

def f(x):
  if x == 0:
    return 1
  elif x%2 == 1:
    return (3*f(x-1))%Mod
  else:
    return (f(x//2)**2)%Mod

def g(x):
  if x == 0:
    return 1
  elif x%2 == 1:
    return (2*g(x-1))%Mod
  else:
    return (g(x//2)**2)%Mod

l = [int(t) for t in list(input())]
n = len(l)

s = 0
k = 0
for i in range(n):
  if l[i] == 0:
    continue
  s = (s + f(n-1-i)*g(k))%Mod
  k += 1
s = (s + g(k))%Mod
print(s)

### FIXED CODE ###

from functools import lru_cache
Mod = 10**9+7

l = [int(t) for t in list(input())]
n = len(l)

@lru_cache(maxsize=10000)
def f(x):
  if x == 0:
    return 1
  elif x%2 == 1:
    return (3*f(x-1))%Mod
  else:
    return (f(x//2)**2)%Mod

@lru_cache(maxsize=10000)
def g(x):
  if x == 0:
    return 1
  elif x%2 == 1:
    return (2*g(x-1))%Mod
  else:
    return (g(x//2)**2)%Mod



s = 0
k = 0
for i in range(n):
  if l[i] == 0:
    continue
  s = (s + f(n-1-i)*g(k))%Mod
  k += 1
s = (s + g(k))%Mod
print(s)
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

def primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = defaultdict(int)  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return primes

PC = [primeCount(a) for a in A]

primes = defaultdict(int)
for pc in PC:
    for p, c in pc.items():
        if c > primes[p]:
            primes[p] = c

ans = 0
for pc in PC:
    b = 1
    for p, c in primes.items():
        b *= pow(p, c - pc[p], MOD)
        b %= MOD
    ans += b

print(ans % MOD)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

def lcm(n, m):
    return n * m // gcd(n, m)

L = A[0]
for a in A:
    L = lcm(L, a)

ans = 0
for a in A:
    ans += L // a

print(ans % MOD)
### BUGGY CODE ###

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

def su(n):
  return n*(n+1)/2

maxx = 0
for i in range(n-k+1):
  m = 0
  m = sum(p[i:i+k])
  if m > maxx:
    maxx = m
    idx = i
s = 0
for i in range(k):
  s += su(p[idx+i])/p[idx+i]
print(s)


### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))

    for i in range(n):
        p[i]=(p[i]+1)/2
    s = [0]
    for i in range(n):
        s.append(s[i]+p[i])
    m = 0
    for i in range(n-k+1):
        if m<s[i+k]-s[i]:
            m = s[i+k]-s[i]
    print(m)

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

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

mod=998244353
if D[0]!=0:
  print(0)
else:
  ans=1
  for i in range(2,n):
    ans*=D.count(i-1)**D.count(i)
    if ans==0:
      print(ans)
      exit()
  print(ans%mod)

### FIXED CODE ###

import collections
n=int(input())
D=list(map(int,input().split()))

mod=998244353
c=collections.Counter(D)

if D[0]!=0 or c[0]!=1:
  print(0)
else:
  ans=c[0]
  node=c[0]
  for i in range(1,n):
    ans*=(c[i-1]**c[i])%mod
    node+=c[i]
    if node==n:
      break
  print(ans%mod)
### BUGGY CODE ###

from functools import reduce

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


def gcd(x, y):
    if x < y:
        x, y = y, x
    while y != 0:
        tmp = x % y
        x = y
        y = tmp
    return x


ans = 1
if N == 2:
    print(max(a))
    exit()


for i in range(N):
    if i == 0:
        n = reduce(gcd, a[1:])
    elif i == N-1:
        n = reduce(gcd, a[:i])
    else:
        n = reduce(gcd, a[:i]+a[i+1:])
    ans = max(ans, n)
print(ans)

### FIXED CODE ###

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


def gcd(x, y):
    if x < y:
        x, y = y, x
    while y != 0:
        tmp = x % y
        x = y
        y = tmp
    return x


ans = 1
if N == 2:
    print(max(a))
    exit()

l = [1] * N
l[0] = a[0]
r = [1] * N
r[N-1] = a[N-1]
for i in range(1, N):
    l[i] = gcd(l[i-1], a[i])
    r[N-1-i] = gcd(r[N-i], a[N-1-i])
    
for i in range(N):
    if i == 0:
        n = r[1]
    elif i == N-1:
        n = l[N-2]
    else:
        n = gcd(l[i-1], r[i+1])
    ans = max(ans, n)
print(ans)
### BUGGY CODE ###

import math
b = list(map(int,input().split()))
ans=0
check=0
i=0
for i in range(b[2]+1):
    if b[2]-i <0:
        break
    check = math.floor((b[0]*(b[2]-i))/b[1]) - b[0]*math.floor((b[2]-i)/b[1])
    if check > ans:
        ans=check
print(ans)

### FIXED CODE ###

import math
b = list(map(int,input().split()))
ans=0
check=0
if b[2]>b[1]-1:
    check = math.floor((b[0]*(b[1]-1))/b[1]) - b[0]*math.floor((b[1]-1)/b[1])
else:
    check = math.floor((b[0]*b[2])/b[1]) - b[0]*math.floor(b[2]/b[1])
if check>ans:
    ans=check
print(ans)
### BUGGY CODE ###

class SegTree:
    def __init__(self,arr,func,unit):
        self.func = func
        self.unit = unit
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [unit]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = func(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i >= 0:
            i = (i - 1) // 2
            self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

    def query(self,l,r):
        l += self.n
        r += self.n
        s = self.unit
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(self.nodes[r-1], s)
            if l & 1:
                s = self.func(s, self.nodes[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return s

n, k = map(int, input().split())
A = [int(input()) for i in range(n)]

MAX = 300001

segt = SegTree([0] * MAX, lambda x, y: max(x, y), 0)
for a in A:
    l = max(0, a - k)
    r = min(MAX, a + k + 1)
    m = segt.query(l, r)
    segt.update(a, m + 1)

print(segt.query(0, MAX))


### FIXED CODE ###

class SegTree:
    def __init__(self,arr,func,unit):
        self.func = func
        self.unit = unit
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [unit]*(2*n-1)
        nodes[n-1:n-1+len(arr)] = arr
        for i in range(n-2,-1,-1):
            nodes[i] = func(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i >= 0:
            i = (i - 1) // 2
            self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

    def query(self,l,r):
        l += self.n
        r += self.n
        s = self.unit
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(self.nodes[r-1], s)
            if l & 1:
                s = self.func(s, self.nodes[l-1])
                l += 1
            l >>= 1
            r >>= 1
        return s

n, k = map(int, input().split())
A = [int(input()) for i in range(n)]

MAX = 300001

segt = SegTree([0] * MAX, lambda x, y: max(x, y), 0)
for a in A:
    l = max(0, a - k)
    r = min(MAX, a + k + 1)
    m = segt.query(l, r)
    segt.update(a, m + 1)

print(segt.query(0, MAX))
### BUGGY CODE ###

K, S = map(int, input().split())

count = 0

for i in range(K + 1):
    for j in range(K + 1):
        for k in range(K + 1):
            if i + j + k == S:
                count += 1

print(count)


### FIXED CODE ###

K, S = map(int, 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 += 1

print(ANS)