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

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

ans = [0] * (N+1)

for j in range(K):
    ans = [0] * (N+1)
    for i in range(N):
        L = max(0, i-A[i])
        R = min(N, i+A[i]+1)
        ans[L] += 1
        ans[R] -= 1
    issame = True
    for i in range(1, N+1):
        ans[i] += ans[i-1]
        if ans[i] != ans[i-1]:
            issame = False
    if issame:
        break
    for i in range(N):
        A[i] = ans[i]

for i in range(N):
    print(ans[i], end=' ')

### FIXED CODE ###

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

ans = [0] * (N+1)

for j in range(K):
    ans = [0] * (N+1)
    for i in range(N):
        L = max(0, i-A[i])
        R = min(N, i+A[i]+1)
        ans[L] += 1
        ans[R] -= 1
    for i in range(1, N+1):
        ans[i] += ans[i-1]
    issame = True
    for i in range(N):
        if i != 0:
            if ans[i-1] != N or ans[i-1] != ans[i]:
                issame = False
        A[i] = ans[i]
    if issame:
        break

for i in range(N):
    print(ans[i], end=' ')
### BUGGY CODE ###

def check(s):
    a_bit=0
    count=0
    for i in s:
        if i=="A":
            a_bit=1
        elif i=="C" and a_bit==1:
            a_bit=0
            count+=1
        else:
            a_bit=0
    print(count)



n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())
    check(s[l-1:r])

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
    
dp =[0 for j in range(n)]


for j in range(n):
    t=0
    if s[j]=="C" and j!=0:
        if s[j-1]=="A":
            t=1

    dp[j]=dp[j-1]+t
        

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

n, m = map(int, input().split())
des = []
first = []
a = 1 ###IMPOSSIBLEフラグ
for i in range(0, m):
	des.append(list(map(int, input().split())))
###ここまで入力
###以下出力
for i in des:
	if i[0] == 1:
		first.append(i[1])
###以上1から行ける場所をfirstに格納
for i in des:
	if first.count(i[0]):
		if i[1] == n:
			print('POSSIBLE')
			a = 0
			break

if a:
	print('IMPOSSIBLE')





### FIXED CODE ###

n, m = map(int, input().split())
des= [0]*(n+1)
a = 1
for i in range(0, m):
	b = (list(map(int, input().split())))
	if b[0] == 1:
		des[b[1]] += 1
		if des[b[1]] == 2:
			print('POSSIBLE')
			a = 0
			break
	if b[1] == n:
		des[b[0]] += 1
		if des[b[0]] == 2:
			print('POSSIBLE')
			a = 0
			break
		
if a:
	print('IMPOSSIBLE')
### BUGGY CODE ###

N, K = map(int, input().split())
E = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
counts = [False]*N
q = [0]
counts[0] = True
r = K
while len(q) > 0:
  i = q.pop(0)
  # get_nexts
  js = E[i]
  jsn = list(filter(lambda j: not(counts[j]), js))
  #print(js, jsn)
  c = K-1-len(js)+len(jsn)
  for j in jsn:
    counts[j] = True
    r = (r*c)%1000000007
    c -= 1
  q.extend(jsn)
print(r)


### FIXED CODE ###

N, K = map(int, input().split())
E = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
counts = [False]*N
q = [0]
counts[0] = True
r = K
while len(q) > 0:
  i = q.pop(0)
  # get_nexts
  js = E[i]
  c = K-1 if i == 0 else K-2
  for j in js:
    if not(counts[j]):
      counts[j] = True
      r = (r*c)%1000000007
      c -= 1
      q.append(j)
print(r)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
K=int(input())
ans=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans+=gcd(i,j,k)
print(ans)  

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K=int(input())
a=[]
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            a.append(gcd(i,j,k))
print(sum(a))
### BUGGY CODE ###

A,B=map(int,input().split())
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)
def gcd(a,b):#最大公約数を返す。Euclid
    if a<b:
        a,b=b,a
    if b==0:
        return a
    return gcd(b,a%b)
c=gcd(A,B)
#print(c)
if c==1:
    print(1)
else:
    sqrtc=int(c**(1/2))
    lf=[0 for i in range(c-1)]#2,3,,,,c
    #print(lf)
    for i in range(sqrtc):
        if lf[i]==0:
            for j in range(i+2,c//(i+2)+1):
                lf[(i+2)*j-2]=1
    #print(lf)
    ans=1
    for i in range(c-1):
        if lf[i]==0 and c%(i+2)==0:
            ans+=1

    #print(c-sum(lf)+1)
    print(ans)


### FIXED CODE ###

A,B=map(int,input().split())
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)
def gcd(a,b):#最大公約数を返す。Euclid
    if a<b:
        a,b=b,a
    if b==0:
        return a
    return gcd(b,a%b)
c=gcd(A,B)
#print(c)
sqrtc=int(c**(1/2))
vc=c
ans=1
for i in range(2,sqrtc+1):
    if vc%i==0:
        ans+=1
        vc/=i
        while vc%i==0:
            vc/=i
if vc!=1:
    ans+=1
print(ans)
### BUGGY CODE ###

from collections import deque
n=int(input())
p=list(map(int,input().split()))
cnt=0
s=deque()
for i in p:
  s.append(i)
  if min(s)==i:
    cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
cnt=0
min=p[0]
for i in p:
  if i<=min:
    cnt+=1
    min=i
print(cnt)
### BUGGY CODE ###

import numpy as np
import copy

N = int(input())  
a = np.array(input().split(), dtype=np.int64)
b = copy.deepcopy(a)
M = np.arange(N) + 1
    
for i in np.arange(N // 2)[::-1]:
    A = a[np.where(M % (i+1) == 0)]
    if (np.sum(A) + a[i]) % 2  == 0:
        b[i] = a[i]
    else:
        b[i] = (a[i] + 1) % 2
        
ans = np.where(b == 1)[0] + 1

print(np.size(ans))

if np.size(ans) > 0:
    print(*ans.astype(np.int32))

### FIXED CODE ###

import numpy as np
import copy

N = int(input())  
a = np.array(input().split(), dtype=np.int32)
M = np.arange(N) + 1
    
for i in np.arange(N // 2)[::-1]:
    A = a[i::i+1]
    if np.sum(A) % 2  == 0:
        a[i] = 0
    else:
        a[i] = 1
        
ans = np.where(a == 1)[0] + 1

print(np.size(ans))

if np.size(ans) > 0:
    print(*ans.astype(np.int32))
### BUGGY CODE ###

import numpy as np


def int_bitmap(n: int, size=32) -> list:
    table = np.array([0] * size)
    for i in range(size):
        table[i] = (n >> i) & 1
    return table


def bin_search(A, start, end):
    left, right = start, end
    while left < right:
        mid = (left + right) // 2
        if max(A[end] - A[mid]) < 2:  # midが条件を満たすとき、左をmidに置き換える
            right = mid
        elif max(A[end] - A[mid]) > 1:  # midを満たさないとき、左をmidに置き換える
            left = mid + 1
    return left


n = int(input())
_A = [int_bitmap(int(i), 20) for i in input().split()]

cul_sum = [int_bitmap(int(0), 20) for _ in range(n + 1)]

ans = 0

# pre-processsing for cul_sum
for i in range(1, n + 1):
    cul_sum[i] = cul_sum[i - 1] + _A[i - 1]

for i in range(1, n + 1):
    # 右端をiとしたときに条件を満たす最長区間を２分探索する
    p = bin_search(cul_sum, 0, i)
    ans += (i - p)

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


n = int(input())
A = [int(i) for i in input().split()]
_sum = 0
_xor = 0
l, r = 0, 0
ans = 0
while l < n:
    while r < n and _sum + A[r] == _xor ^ A[r]:
        _sum += A[r]
        _xor ^= A[r]
        r += 1
    ans += r - l
    _sum -= A[l]
    _xor ^= A[l]
    if l == r:
        r += 1
    l += 1

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

import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(71):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 71
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 71
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(1009):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 1009
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 1009
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

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

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result




n = int(input())
A = list(map(int, input().split()))
AS = sorted(list(set(A)))
n = AS[-1]
r = AS[0]
combM = cmb(n, r)

for i in range(1,len(AS)):
    tempr = AS[i]
    tempc = cmb(n, tempr)
    if combM >= tempc:
        break
    r = tempr
    combM = tempc


print(str(n) + ' ' + str(r))



### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
AS = sorted(list(set(A)))
n = AS[-1]
checkAS = len(AS)-1
nHalf = n/2
min = 10**10


for i in range(checkAS):
    temp = abs(AS[i]-nHalf)
    if min > temp:
        r = AS[i]
        min = temp

print(str(n) + ' ' + str(r))
### BUGGY CODE ###

from collections import deque
n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kinds=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kinds:
        kinds[td[i][0]].append(td[i][1])
    else:
        kinds[td[i][0]]=deque()
        kinds[td[i][0]].append(td[i][1])
l=len(kinds)
ans+=(l**2)

ans_=ans
for i in range(k,n):
    if td[i][0] not in kinds:
        mi=[1000000000,1000000000]
        for j in kinds:
            if len(kinds[j])>1:
                if mi[1]>kinds[j][-1]:
                    mi=[j,kinds[j][-1]]
        if mi==[1000000000,1000000000]:
            break
        else:
            ans=ans-l**2+(l+1)**2-mi[1]+td[i][1]
            kinds[mi[0]].pop()
            kinds[td[i][0]]=deque()
            kinds[td[i][0]].append(td[i][1])
            ans_=max(ans,ans_)
            l+=1

print(ans_)


### FIXED CODE ###

n,k=map(int,input().split())
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

ans=0
kl=dict()
for i in range(k):
    ans+=td[i][1]
    if td[i][0] in kl:
        kl[td[i][0]]+=1
    else:
        kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
now=k-1
for i in range(k,n):
    if td[i][0] not in kl:
        #最小を求めるのをもっと早く
        while now>=0:
            if kl[td[now][0]]>1:
                mi=td[now]
                kl[mi[0]]-=1
                now-=1
                break
            now-=1
        if now==-1:
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1]
            kl[td[i][0]]=1
            ans_=max(ans,ans_)
            l+=1

print(ans_)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
*h, = map(int, input().split())
dp = [0] + [float('inf')]*(N-1)
for j in range(1,N):
    for i in range(max(0,j-K),j):
        dp[j] = min(dp[j],dp[i] + abs(h[j]-h[i]))
        # print("j -> {} || i -> {} || dp -> {} || h[j] -> {} || h[i] -> {}".format(j, i, dp, h[j], h[i]))
print(dp[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())
*h, = map(int, input().rstrip().split())
dp = [0] + [float('inf')]*(N-1)
for j in range(1,N):
    for i in range(max(0,j-K),j):
        dp[j] = min(dp[j],dp[i] + abs(h[j]-h[i]))
        # print("j -> {} || i -> {} || dp -> {} || h[j] -> {} || h[i] -> {}".format(j, i, dp, h[j], h[i]))
print(dp[-1])
### BUGGY CODE ###

S = int(input().strip())
for i in range(int(S**0.5), 0, -1):
  if S % i == 0:
    print(0,0,0,i,S//i,0)
    break


### FIXED CODE ###

s = int(input().strip())
m = int(1e9)
if s % m == 0:
  x = 0
  y = s//m
else:
  x = m-(s%m)
  y = (s//m)+1
print(0,0,1000000000,1,x,y)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = [int(i) for i in input().split()]
B = sorted(A.copy(), reverse=True)

ans = 1
for d in range(B[0], 0, -1):
    count = 0
    for b in B:
        if b % d != 0:
            count += 1
            if count >= 2:
                break
    if count < 2:
        ans = d
        break

print(ans)

### FIXED CODE ###

# 解けなかった...orz

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

def gcd(i, j):
    if i <= 0:
        return j
    elif j <= 0:
        return i

    while i != j:
        if i < j:
            j %= i
            if j == 0: return i
        else:
            i %= j
            if i == 0: return j
    return i

# M = [0] * N
L = [0] * (N+1)
R = [0] * (N+1)
# L[0] = 0
# R[N] = 0

for i in range(N):
    L[i+1] = gcd(L[i], A[i])
    R[N-i-1] = gcd(R[N-i], A[N-i-1])

res = max(gcd(L[i], R[i+1]) for i in range(N))
print(res)
### BUGGY CODE ###

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

l = []
r = []
if N % 2 == 0:
    for i, a in enumerate(A):
        if i % 2 == 1:
            l.append(a)
        else:
            r.append(a)
        l.reverse()
else:
    for i, a in enumerate(A):
        if i % 2 == 0:
            l.append(a)
        else:
            r.append(a)
        l.reverse()

ans = l + r
print(" ".join(ans))


### FIXED CODE ###

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

l = []
r = []
flag = False
if N % 2 == 0:
    for i in range(N-1, 0, -2):
        if flag:
            print(" ", end="")
        print(A[i], end="")
        flag = True
    for i in range(0, N, 2):
        if flag:
            print(" ", end="")
        print(A[i], end="")
else:
    for i in range(N-1, -1, -2):
        if flag:
            print(" ", end="")
        print(A[i], end="")
        flag = True
    for i in range(1, N, 2):
        if flag:
            print(" ", end="")
        print(A[i], end="")


print()
### BUGGY CODE ###

n = int(input())

# alp = ["a","b","c","d","e",
# "f","g","h","i","j",
# "k","l","m","n","o",
# "p","q","r","s","t",
# "u","v","w","x","y","z"]
#
ans = 0
# array1 = np.zeros().reshape( n,10)


# list1 = []
list_s = []

for i in range(n):
    s = input()
    s = ''.join(sorted(s))
    ans += list_s.count(s)

    list_s.append(s)

print(int(ans))


### FIXED CODE ###

n = int(input())

ans = 0
ans_dict = {}

for i in range(n):
    s = input()
    s = ''.join(sorted(s))
    if(s in ans_dict):
        ans += ans_dict[s]
        ans_dict[s] += 1
    else:
        ans_dict[s] = 1
        
print(int(ans))
### BUGGY CODE ###

s = input()
Q = int(input())
lq = [input().split() for _ in range(Q)]

flg = 0 # 0:sonomama 1:gyakuten
for q in lq:
    if q[0] == "1":
        if flg == 0:
            flg = 1
        else:
            flg = 0
    elif q[0]=="2":
        tmp = q[2]
        if (q[1] == "1" and flg ==0) or (q[1] == "2" and flg ==1):
            tmp += s
            s = tmp
        elif (q[1] == "2" and flg == 0) or (q[1] == "1" and flg == 1):
            s += tmp

if flg==1:
    s = s[::-1]
print(s)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    s = input()
    s = s[0:len(s)-1]
    Q = int(input())
    head = []
    tail = []

    flg = 0 # 0:sonomama 1:gyakuten
    for _ in range(Q):
        q = input().split()
        if q[0] == "1":
            if flg == 0:
                flg = 1
            else:
                flg = 0
        elif q[0]=="2":
            index,tmp = q[1],q[2]
            if (index == "1" and flg ==0) or (index == "2" and flg ==1):
                head.append(tmp)
            elif (index == "2" and flg == 0) or (index == "1" and flg == 1):
                tail.append(tmp)

    s1 = "".join(head)
    s1 = s1[::-1]
    s2 = "".join(tail)
    ans = s1 + s + s2
    if flg == 1:
        ans = ans[::-1]

    print(ans)

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

s = input()
array = [0]*(len(s)+1)
mod = 2019

for i in range(len(s)):
    array[i] = int(s[i:len(s)]) % mod
    
array[len(s)] = 0

cnt = 0

for i in range(0, len(array)-1):
    for j in range(i+1, len(array)):
        if array[i] == array[j]:
            cnt += 1
            
print(cnt)

### FIXED CODE ###

s = input()
mod = 2019
array = [0]*(len(s)+1)

for i in range(len(s)):
    array[i+1] = (array[i] + pow(10,i,mod)*int(s[len(s)-(i+1)])) % mod
    

    
array.sort()

cnt = 0
w = 1

for i in range(0, len(array)-1):
    if array[i] == array[i+1]:
        w += 1
    else:
        if w >= 2:
            cnt += w*(w-1)/2
            w = 1
            
if w != 1:
    cnt += w*(w-1)/2
    
print(int(cnt))
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

ABC = []
for a in A:
    for b in B:
        for c in C:
            ABC.append(a+b+c)
ABC = sorted(ABC,reverse=True)
for k in range(K):
    print(ABC[k])


        

### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

AB = []
for a in A:
    for b in B:
            AB.append(a+b)
AB = sorted(AB,reverse=True)[:K]
C = sorted(C,reverse=True)
ABC = []

for c in C:
    for ab in AB:
        ABC.append(c + ab)
ABC = sorted(ABC,reverse=True)        
print(*ABC[:K],sep="\n")
### BUGGY CODE ###

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

### FIXED CODE ###

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

n = int(input())
num = list(map(int, input().split()))
list = []
list.append(num[0])
count = 1

for i in range(1,n):
  if num[i]<=min(a for a in list):
    count += 1
    list.append(num[i])
  else:
    list.append(num[i])

print(count)

### FIXED CODE ###

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

min_n = num[0]
count = 1
for i in range(1,n):
  if num[i]<=min_n:
    count += 1
    min_n = num[i]
    
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from functools import lru_cache
sys.setrecursionlimit(10 ** 8)

shina = []


@lru_cache(maxsize=None)
def solve(i, j):
    if i == len(shina):
        return 0

    if shina[i][0] > j:
        return solve(i + 1, j)

    return max(solve(i + 1, j), solve(i + 1, j - shina[i][0]) + shina[i][1])


def main():
    N, W = [int(x) for x in input().split()]
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    ans = solve(0, W)

    print(ans)

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


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

def extractMax(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:  # ???????????????
        v = A[i]
        rv = 0
        lv = 0
        r = (i + 1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x


def insert(A, n):
    i = len(A)
    A.append(n)
    while i > 0:  # ???????????????
        p = int((i + 1) / 2) - 1
        v = A[i]
        pv = A[p]
        if pv < v:  # ???????????§??????
            A[p] = v
            A[i] = pv
            i = p
        else:
            break

heap = []
while True:
    s = input().split()
    if s[0] == "end":
        break
    elif s[0] == "extract":
        print(extractMax(heap))
    elif s[0] == "insert":
        insert(heap, int(s[1]))


### FIXED CODE ###

import sys


def extract_max(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:
        v = A[i]
        rv = 0
        lv = 0
        r = (i + 1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x


def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


def main():
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())
    S = []
    for cmd in cmds:  # input()
        if cmd[0] == "i":
            insert(S, int(cmd[7:]))

        elif cmd == "extract":
            a = extract_max(S)
            print(a)

        elif cmd == "end":
            break


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

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

count = 0
for i in range(n):
    if p[i] <= min(p[:i+1]):
        count +=1
    else:
        pass
print(count)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]
small = p[0]
count = 0
for i in range(n):
    if p[i] <= small:
        count +=1
    else:
        pass
    small = min(small,p[i])
print(count)
### BUGGY CODE ###

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

from collections import defaultdict
d = defaultdict(int)

for i in range(1, n):
    for j in range(i+1, n+1):
        if i <= x and j >= y:
            dis = (x-i)+(j-y)+1
        elif j <= x or i >= y:
            dis = j - i
        elif i <= x and j >= x:
            dis = (x-i)+min(j-x, y-j+1)
        elif i <= y and j >= y:
            dis = min(y-i, i-x+1)+(j-y)
        elif i >= x and j <= y:
            dis = min(j-i, (i-x)+1+(y-j))
        d[dis] += 1
            

for i in range(1, n):
    print(d[i])

### FIXED CODE ###

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

from collections import defaultdict
d = defaultdict(int)

for i in range(1, n):
    for j in range(i+1, n+1):
        if i <= x and j >= y:
            dis = (x-i)+(j-y)+1
        elif j <= x or i >= y:
            dis = j - i
        elif i <= x and j >= x:
            dis = (x-i)+min(j-x, y-j+1)
        elif i <= y and j >= y:
            dis = min(y-i, i-x+1)+(j-y)
        elif i >= x and j <= y:
            dis = min(j-i, (i-x)+1+(y-j))
        d[dis] += 1
            

for i in range(1, n):
    print(d[i])
### BUGGY CODE ###

import re
n,q=map(int,input().split())
s=list(input())

for i in range(q):
    l,r=[int(i)-1 for i in input().split()]
    string="".join(s[l:r+1])
    ans=re.findall("AC",string)
    print(len(ans))

### FIXED CODE ###

import re
n,q=map(int,input().split())
s=input()

a=[0]*(n+1)
for i in range(1,n+1):
    # print(s[i-1:i+1])
    if s[i-1:i+1]=="AC":
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]

for i in range(q):
    l,r=[int(i) for i in input().split()]
    print(a[r-1]-a[l-1])