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

N, Q = map(int, input().split())
S = input()
Left = []
Right = []

for i in range(Q):
    l, r = map(int, input().split())
    Left.append(l)
    Right.append(r)

def search_AC(left, right):
    String = S[left - 1 :right]
    count = 0
    
    for i in range(len(String)-1):
        if (String[i] == 'A' and String[i + 1] == 'C'):
            count += 1
        
    return (count)

for i in range(Q):
    answer = search_AC(Left[i], Right[i])
    print(answer)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
S_con = [0 for i in range(len(S))]

def convert_N_AC():
    
    for i in range(1, len(S)):
        tmp = 0
        if (S[i - 1 : i + 1] == 'AC'):
            tmp = 1
        S_con[i] += tmp + S_con[i-1]

convert_N_AC()

for i in range(Q):
    l, r = map(int, input().split())
    answer = S_con[r - 1] - S_con[l - 1]
    print(answer)
### BUGGY CODE ###

H, W=map(int, input().split())
S=[]
S.append("".join(["#" for _ in range(W+2)]))
S.extend(["#"+input()+"#" for _ in range(H)])
S.append("".join(["#" for _ in range(W+2)]))
co1=[[0 for _ in range(W+2)] for _ in range(H+2)]
co2=[[0 for _ in range(W+2)] for _ in range(H+2)]

for i in range(1, H+2):
    ppos=0
    for j in range(W+2):
        if S[i][j]=="#":
            if S[i][j-1]==".":
                for k in range(ppos, j):
                    co1[i][k]=j-ppos
            ppos=j+1

for j in range(1, W+2):
    ppos=0
    for i in range(H+2):
        if S[i][j]=="#":
            if S[i-1][j]==".":
                for k in range(ppos, i):
                    co2[k][j]=i-ppos
            ppos=i+1

ans=0
for i in range(1, H+2):
    for j in range(1, W+2):
        ans=max(ans, co1[i][j]+co2[i][j]-1)
print(ans)


### FIXED CODE ###

H, W=map(int, input().split())
frame=["".join(["#" for _ in range(W+2)])]
S=frame+["#"+input()+"#" for _ in range(H)]+frame
score=[[0 for _ in range(W+2)] for _ in range(H+2)]
for i in range(H+2):
  sharp_j=0
  for j in range(W+2):
    if S[i][j]=="#":
      for k in range(sharp_j+1, j):
        score[i][k]+=j-sharp_j-1
      sharp_j=j
for j in range(W+2):
  sharp_i=0
  for i in range(H+2):
    if S[i][j]=="#":
      for k in range(sharp_i+1, i):
        score[k][j]+=i-sharp_i-2
      sharp_i=i
ans=0
for i in range(H+2):
  for j in range(W+2):
    ans=max(ans, score[i][j])
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
X.sort(key = lambda x: x[2])
X.append([-1, 1, X[-1][2] + 1])

def quitConst(t):
  nextx = [x for x in X if x[1] > t + x[2] or x[0] == -1]
  return nextx
def startConst(t):
  nextx = [x for x in X if x[0] <= t + x[2] or x[0] == -1]
  return nextx
for _ in range(Q):
  current = 0
  start = int(input())
  X = quitConst(start)
  XX = startConst(start)
  for x in XX:
    current = x[2]
    if x[0] <= current + start < x[1]:
      break
  if current == XX[-1][2]:
    print(-1)
  else:
    print(current)

### FIXED CODE ###

from bisect import bisect_left as bl
N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
X.sort(key = lambda x: x[2])
Y = [int(input()) for _ in range(Q)]
res = [-1] * Q
jump = [-1] * Q
for s,t,x in X:
  l=bl(Y,s - x)
  r=bl(Y,t - x)
  while l < r:
    s = jump[l]
    if s == -1:
      res[l] = x
      jump[l] = r
      l += 1
    else:
      l = s
print(*res,sep = '\n')
### BUGGY CODE ###

n, m, q = [int(x) for x in input().split()]

t_list = []
c_list = []
for _ in range(n + 1):
    t_list.append([0] * (n + 1))
    c_list.append([0] * (n + 1))

for _ in range(m):
    l, r = [int(x) for x in input().split()]
    t_list[l][r] += 1

for i in range(1, n + 1):
    for j in range(1, n + 1):
        c_list[i][j] = t_list[i][j] + c_list[i][j - 1]

for _ in range(q):
    l, r = [int(x) for x in input().split()]
    ans = 0
    for j in range(l, r + 1):
        ans += c_list[j][r] - c_list[j][l - 1]
    print(ans)

### FIXED CODE ###

n, m, q = [int(x) for x in input().split()]

t_list = [[0] * (n + 1) for i in range(n + 1)]
c_list = [[0] * (n + 1) for i in range(n + 1)]

for _ in range(m):
    l, r = [int(x) for x in input().split()]
    t_list[l][r] += 1

for i in range(1, n + 1):
    for j in range(1, n + 1):
        c_list[i][j] = t_list[i][j] + c_list[i][j - 1] + c_list[i - 1][j] - c_list[i - 1][j - 1]

for _ in range(q):
    l, r = [int(x) for x in input().split()]
    print(c_list[r][r] - c_list[l - 1][r] - c_list[r][l - 1] + c_list[l - 1][l - 1])
### BUGGY CODE ###

n = int(input())
a = list(input().split())
b = []
for i in a:
    if n%2==1:
        if int(i)%2==1: b.insert(0,i)
        else:  b.append(i)
    else:
        if int(i)%2==0: b.insert(0,i)
        else:  b.append(i)
print(" ".join(b))

### FIXED CODE ###

n = int(input())
a = list(input().split())
b = []
if n%2==1:
    b = a[::-2]+a[1::2]
else:
    b = a[::-2]+a[::2]
print(" ".join(b))
### BUGGY CODE ###

import math
n=int(input())
a=list(map(int,input().split()))
q=int(input())
for i in range(q):
    k=int(input())
    t=0
    max=n-1
    min=0
    while max-min>1:
        nn=math.floor((max-min)/2)
        if a[nn]==k:
            t=1
            print("1")
            break
        elif a[nn]>k:
            min=nn
        else :
            max=nn
    if t==0:
        print("0")


### FIXED CODE ###

import math
n=int(input())
a=list(map(int,input().split()))
q=int(input())
for i in range(q):
    k=int(input())
    t=0
    max=n-1
    min=0
    while max-min>1:
        nn=math.floor((max+min)/2)
        if a[nn]==k:
            t=1
            print("1")
            break
        elif a[nn]<=k:
            min=nn
        elif a[nn]>=k:
            max=nn
    if t==0:
        if a[max]==k or a[min]==k:
            t=1
            print("1")
        else:
            print("0")
### BUGGY CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

P = 998244353

fact = [1]
for i in range(1, 10**6):
  fact.append((fact[i-1] * i) % P)


def inv(x):
  return pow(x, P-2, P)

def comb(n, k):
  assert 0 <= k <= n
  return (fact[n] * inv(fact[k]) * inv(fact[n-k])) % P

setrecursionlimit(100000)

N, A, B, K = reads()

result = 0
for x in range(N+1):
  if (K - A * x) % B != 0:
    continue
  y = (K - A * x) // B
  if not (0 <= y <= N):
    continue
  result = (result + comb(N, x) * comb(N, y)) % P

print(result)

### FIXED CODE ###

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

P = 998244353

N, A, B, K = reads()

def inv(n):
  return pow(n, P-2, P)

fact = [1] * (N+1)
for i in range(1, N+1):
  fact[i] = fact[i-1] * i % P

invfact = [inv(fact[N])] * (N+1)
for i in range(N, 0, -1):
  invfact[i-1] = invfact[i] * i % P

def comb(n, k):
  # assert 0 <= k <= n
  return fact[n] * invfact[k] * invfact[n-k] % P

result = 0
for x in range(N+1):
  y, r = divmod(K - A * x, B)
  if r == 0 and 0 <= y <= N:
    result = result + comb(N, x) * comb(N, y) % P

print(result % P)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
import collections 
c = collections.Counter(a)
for i in range(1,n+1):
    print(c[i])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
max_a = max(a)
tmp_a = a.copy()
count = 0
for i in range(n):
    if tmp_a[i] == max_a:
        count += 1

if count == 1:
    for i in range(len(a)):
        tmp_a = a.copy()
        if tmp_a[i] == max_a:
            del tmp_a[i]
            print(max(tmp_a))
        else:
            print(max_a)
else:
    for i in range(len(a)):
        print(max_a)



### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

sorted_a = sorted(a)
first_a = sorted_a[-1]
second_a = sorted_a[-2]

for i in range(len(a)):
    if a[i] == first_a:
        print(second_a)
    else:
        print(first_a)
### BUGGY CODE ###

n=int(input())
ans=10**11
for i in range(1,n+1):
    if n%i == 0:
        a=i
        b=n//i
        a_len=len(str(a))
        b_len=len(str(b))
        ans=min(ans,max(a_len,b_len))
print(ans)

### FIXED CODE ###

import math

n=int(input())
ans=10**11
for i in range(1,math.floor(math.sqrt(n)+1)):
    if n%i == 0:
        a=i
        b=n//i
        a_len=len(str(a))
        b_len=len(str(b))
        ans=min(ans,max(a_len,b_len))
print(ans)
### BUGGY CODE ###

import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n, w = LI()
wv = LIR(n)
weight = [wv[i][0] for i in range(n)]
value = [wv[i][1] for i in range(n)]
# dp[i][j] : 重さ制限 j 、品物 i までを選べる状態での価値の最大値
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(w + 1):
        if j - weight[i] >= 0:  # 品物 i が選べるかどうか
            dp[i + 1][j] = max(
                dp[i][j],  # 選ばない
                dp[i][j - weight[i]] + value[i]  # 選ぶ
            )
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[n][w])


### FIXED CODE ###

n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
w = [wv[i][0] for i in range(n)]
v = [wv[i][1] for i in range(n)]
inf = float('inf')
# dp[i][weight] 
# := i-1番目までの品物で重さweightを超えないように選んだときの価値の総和の最大値
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
for i in range(n):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[n][W])
### BUGGY CODE ###

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

count = 0
for i in range(n):
    for j in range(i + a[i], n):
        if a[i] + a[j] == j - i:
            count += 1

print(count)

### FIXED CODE ###

import numpy as np
from collections import defaultdict

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

idxs = np.arange(n)
L, R = idxs + a, idxs - a

count = 0
d = defaultdict(int)
for i in range(n-1):
    d[L[i]] += 1
    count += d[R[i+1]]

print(count)
### BUGGY CODE ###

H,N = map(int,input().split())
Damage = []
Cost = []


DP = [0] * (H+1)



for i in range(N):
    a,b = map(int,input().split())
    Damage.append(a)
    Cost.append(b)
    
#print(DP)


# DP[i] = best magic points to do i damage

for i in range(1,len(DP)):
    best = pow(10,9)
    for spell in range(N):
#        print(spell,i, Damage[spell], Cost[spell])
        best = min(best,DP[max(0,i-Damage[spell])]+Cost[spell])
    DP[i] = best




print (DP[H])



### FIXED CODE ###


     

import math



H,N = map(int,input().split())
Damage = []
Cost = []


DP = [0] + [pow(10,9)] * (H+1)



for i in range(N):
    a,b = map(int,input().split())
    Damage.append(a)
    Cost.append(b)
    
#print(DP)


# DP[i] = min magic points to do i damage

for i in range(1,len(DP)):
    for spell in range(N):
        DP[i] = min(DP[i],DP[max(0,i-Damage[spell])]+Cost[spell])




print (DP[H])
### BUGGY CODE ###

#13:12
n,q = map(int,input().split())
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  event.append([s-x,1,x])
  event.append([t-x,0,x])
event.sort()
t = 0
now = set()
for _ in range(q):
  d = int(input())
  if t == 2*n:
    print(-1)
    continue
  while event[t][0] <= d:
    if event[t][1] == 1:
      now.add(event[t][2])
    else:
      now.remove(event[t][2])
    t += 1
    if t == 2*n:
      break
  try:
    print(min(now))
  except:
    print(-1)

### FIXED CODE ###

#13:12
n,q = map(int,input().split())
import heapq
import sys
input = sys.stdin.readline
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  heapq.heappush(event,(s-x,t-x,x))
t = 0
now = []
for _ in range(q):
  d = int(input())
  if event:
    while event[0][0] <= d:
      tmp = heapq.heappop(event)
      heapq.heappush(now,(tmp[2],tmp[1]))
      if not event:
        break
  if now:
    while now[0][1] <= d:
      heapq.heappop(now)
      if not now:
        print(-1)
        break
    else:
      print(now[0][0])
  else:
    print(-1)
### BUGGY CODE ###

mst_l = [chr(i) for i in range(97,97+26)]

n = int(input())
l = [input() for _ in range(n)]
l = ["".join(map(str, [x.count(a) for a in mst_l])) for x in l]
result = 0
for i in range(n-1):
    result += l[i+1:].count(l[i])
print(result)

### FIXED CODE ###

from math import factorial
from collections import Counter
 
def conb(n):
    if n <= 1:
        return 0
    else:
        return factorial(n) // factorial(n-2) // factorial(2) 

n = int(input())
S = [''.join(sorted(list(input()))) for i in range(n)]

print(int(sum([conb(i) for i in Counter(S).values()])))
### BUGGY CODE ###

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

if N == 1:
    print(P)
else:
    ans = 1
    for x in range(1, P):
        if P % (x**N) == 0:
            ans = max(ans, x)
        if x**N > P:
            break
    print(ans)

### FIXED CODE ###

from collections import Counter

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

# n以下の全ての素数のセットを返す関数
def prime_set(n):
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5) + 1):
        primes.difference_update(range(i*2, n+1, i))
    return primes

# nを素因数分解して素因数の全リストを返す関数
def prime_factors(n):
    f = []
    for i in prime_set(int(n**0.5) + 1):
        while n % i == 0:
            f.append(i)
            n //= i
    if n > 1:
        f.append(n)
    return f

c = Counter(prime_factors(P))
ans = 1

for x in c.keys():
    ans *= pow(x, int(c[x]//N))

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

import queue
def main():
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = [0]*n
    t = [[i+1, i-1] for i in range(n)]
    t[x].append(y)
    t[y].append(x)
    q = queue.Queue()
    for i in range(n):
        f = [True]*n
        f[i] = False
        q.put([i, 0])
        while not q.empty():
            a, b = q.get()
            for v in t[a]:
                if 0 < v and v < n:
                    if f[v]:
                        if i < v:
                            ans[b + 1] += 1
                        f[v] = False
                        if i < v or (i <= (x+y+1)//2 and x <= v):
                            q.put([v, b+1])
    for i in range(1, n):
        print(ans[i])
if __name__ == "__main__":
    main()

### FIXED CODE ###

import queue
def main():
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = [0]*n
    t = [[i+1, i-1] for i in range(n)]
    t[x].append(y)
    t[y].append(x)
    for i in range(n):
        for j in range(i+1, n):
            if j <= x:
                ans[j-i] += 1
            elif j <= y:
                buf = min(j-i, abs(i-x) + 1 + (y-j))
                ans[buf] += 1
            else:
                buf = min(y-i, abs(x-i)+1)
                ans[buf + (j-y)] += 1
    for i in range(1, n):
        print(ans[i])
if __name__ == "__main__":
    main()
### BUGGY CODE ###

mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
for i in range(1,n+1):
	l = 0
	if A.count(i) > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
				if len(p) > 1:
					break
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	t *= (n+1-k)%mod
	t %= mod
	t *= pow(k+1,mod-2,mod)
	t %= mod
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		d *= (n+p[0]-p[1]-k+1)%mod
		d %= mod
		d *= pow(k,mod-2,mod)
		d %= mod
		print((t - d)%mod)
	else:
		print(t%mod)



### FIXED CODE ###

from collections import Counter
mod = 10**9 + 7
n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
l = 0
for i in range(1,n+1):
	if C[i] > 1:
		l = i
		p = []
		for j in range(n+1):
			if A[j] == l:
				p.append(j)
				if len(p) > 1:
					break
		break
	if l:
		break

t = 1
d = 1
for k in range(n+1):

	t *= (n+1-k)%mod
	t %= mod
	t *= pow(k+1,mod-2,mod)
	t %= mod
	if not k:
		print(n)
	elif k <= n+p[0]-p[1]:
		d *= (n+p[0]-p[1]-k+1)%mod
		d %= mod
		d *= pow(k,mod-2,mod)
		d %= mod
		print((t - d)%mod)
	else:
		print(t%mod)
### BUGGY CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()
compare_list = []
compare_dict = {}

for i in range(M):
  [B, C] = list(map(int, input().split(' ')))
  if C not in compare_list:
    compare_list.append(C)
    compare_dict['{}'.format(C)] = B
  else:
    compare_dict['{}'.format(C)] += B
  
compare_list.sort()

ans = 0
for i in range(N):
  if card_list[-1] > compare_list[-1]:
    ans += card_list.pop()
  elif compare_dict['{}'.format(compare_list[-1])] > 0:
    ans += compare_list[-1]
    compare_dict['{}'.format(compare_list[-1])] -= 1
    if compare_dict['{}'.format(compare_list[-1])] == 0:
      tmp = compare_list.pop()
  if compare_list == []:
    ans += sum(card_list[(i + 1):])
    break
      
print(ans)

### FIXED CODE ###

[N, M] = list(map(int, input().split(' ')))
card_list = list(map(int, input().split(' ')))

card_list.sort()
compare_list = []

for i in range(M):
  (B, C) = list(map(int, input().split(' ')))
  compare_list.append((C,B))
    
compare_list.sort()

ans = 0
for i in range(N):
  if compare_list == []:
    ans += sum(card_list[i:])
    break
  if card_list[-1] > compare_list[-1][0]:
    ans += card_list.pop()
  elif compare_list[-1][1] > 0:
    ans += compare_list[-1][0]
    tmp = compare_list.pop()
    a = tmp[0]
    b = tmp[1]
    if b != 1:
      compare_list.append((a,b-1)) 
      
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(N//R + 1):
    for j in range(N//G + 1):
        tmp = i*R + j*G
        if tmp == N:
            ans += 1
        elif tmp < N and (N - (tmp)) % B == 0:
            ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
 
ans = 0
for i in range(N//R + 1):
    for j in range(N//G + 1):
        if i*R + j*G > N:
            break
        if i*R + j*G <= N and (N - (i*R + j*G)) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

num_r,num_c = map(int,input().split())
field = [input() for i in range(num_r)]
q = []
seen = [0]*(num_c*num_r)
count = 0

for i in range(num_r):
  for j in range(num_c):
    if field[i][j] == "#":
      seen[i*num_c+j] = 1
      q.append([i,j])

while q:
  tank = []
  for i in q:
    r = i[0]
    c = i[1]
    if (0<=r-1) and (seen[(r-1)*num_c+c] == 0):
      tank.append([r-1,c])
      seen[(r-1)*num_c+c] = 1
    if (r+1<num_r) and (seen[(r+1)*num_c+c] == 0):
      tank.append([r+1,c])
      seen[(r+1)*num_c+c] = 1
    if (0<=c-1) and (seen[r*num_c+(c-1)] == 0):
      tank.append([r,c-1])
      seen[r*num_c+(c-1)] = 1
    if (c+1<num_c) and (seen[r*num_c+(c+1)] == 0):
      tank.append([r,c+1])
      seen[r*num_c+(c+1)] = 1
   
  count = count + 1
  q = tank

print(count-1)

### FIXED CODE ###

def main():
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        a.append(input())

    used = [True]*(h*w)

    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                p.append(i*w+j)
                used[i*w+j] = False


    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

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

import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
S =sum(A)
cut = []
for k in range(N):
  cut.append(K*A[k]//S)

length = []
for k in range(N):
  length.append([A[k] / (cut[k]+1), k])

length.sort(key = lambda x: x[0], reverse=True)

def nibun_insert(lis, item):
  end = len(lis)
  start = 0
  now = (end+start)//2
  while end > start+1:
    if lis[now][0] > item[0]:
      start = 0 + now
      now = (now + end)//2
    else:
      end = 0 + now
      now = (now + start)//2
  return lis[:now+1] + [item] + lis[now+1:]
  

C = sum(cut)
res = min(K - C, N)
length = length[:res+1]
for k in range(res):
  cut[length[0][1]] += 1
  length[0][0] = length[0][0]*cut[length[0][1]]/(cut[length[0][1]]+1)
  if length[0][0] < length[1][0]:
    length = nibun_insert(length[1:], length[0])
  length = length[:-1]

print(math.ceil(length[0][0]))


### FIXED CODE ###

import math
from collections import deque
N, K = map(int, input().split())
A = list(map(int, input().split()))
S =sum(A)
cut = []
for k in range(N):
  cut.append(K*A[k]//S)

length = []
for k in range(N):
  length.append([A[k] / (cut[k]+1), k])

length.sort(key = lambda x: x[0], reverse=True)

def nibun_insert(lis, item):
  end = len(lis)
  start = 0
  now = (end+start)//2
  while end > start+1:
    if lis[now][0] > item[0]:
      start = 0 + now
      now = (now + end)//2
    else:
      end = 0 + now
      now = (now + start)//2
  return deque(lis[:now+1] + [item] + lis[now+1:])
  

C = sum(cut)
res = min(K - C, N)
length = length[:res+1]
length = deque(length)
for k in range(res):
  a = length.popleft()
  cut[a[1]] += 1
  a[0] = a[0]*cut[a[1]]/(cut[a[1]]+1)
  if a[0] <= length[-1][0]:
    length.append(a)
  elif a[0] >= length[0][0]:
    length.appendleft(a)
  else:
    length = nibun_insert(list(length), list(a))
  length.pop()

print(math.ceil(length.popleft()[0]))
### BUGGY CODE ###

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

i = n - k
score_prev = 1
for i in range(k):
    score_prev *= A[i]
#print(score_prev)
for i in range(k, n):
    score_now = score_prev*A[i]//A[i-k]
#    print(score_now)
    if score_now > score_prev:
        print('Yes')
    else:
        print('No')
    score_prev = score_now

### FIXED CODE ###

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

for i in range(k, n):
    if A[i] > A[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))
s = []
f = []

for i in range(k-1,n):
    z = 0
    c = 1
    while z < k:
        c = c * arr[i-z]
        z += 1

    s.append(c)
    
l = len(s)
for i in range(1,l):
    if s[i]>s[i-1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

for i in range(n-k):
    if (arr[i]<arr[i+k]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mul = [1]
for i in range(n):
    mul.append(mul[i]*a[i])

total = mul[-1]
pre = mul[k]
for i in range(k+1, n+1):
    now = mul[i] // mul[i-k]
    if pre < now:
        print('Yes')
    else:
        print('No')
    pre = now

### FIXED CODE ###

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

for i in range(k, n):
    if a[i] > a[i-k]:
        print('Yes')
    else:
        print('No')