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

from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
ap = defaultdict(list)
for i in range(n):
    ap[i - a[i]].append(i)

ans = 0
for i in range(n):
    for aj in ap[a[i] + i]:
        if max(i + 1, a[i] + 1) <= aj < n:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
ap = defaultdict(int)
for i in range(n):
    ap[i - a[i]] += 1

ans = 0
for i in range(n):
    ans += ap[a[i] + i]
print(ans)
### BUGGY CODE ###

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

ans=0
for _ in range(10**5):
    count=0
    for i in range(n):
        if a[i]%2!=0:
            a[i]*=3
            count+=1
        else:
            a[i]=a[i]//2
            break
    if count==n:
        break
    if count!=n:
        ans+=1
print(ans)

### FIXED CODE ###

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

b=[]
for i in range(1,30):
    b.append(2**i)
#print(b)
ans=0
u=len(b)
for i in range(n):
    for j in range(u):
        if a[i]%b[j]==0:
            ans+=1
print(ans)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n
        # one -index
        # self.g  = [set([i]) for i in range(n+1)]
        # self.gp = [set([i]) for i in p]

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # self.g[y+1] = self.g[y+1] | self.g[x+1]
            # self.gp[y+1]= self.gp[y+1]| self.gp[x+1]
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

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


n,m = map(int,input().split())
p = [set([int(i)]) for i in input().split()]
r = [set([int(i)]) for i in range(1,n+1)]
uf = UnionFind(n)
for i in range(m):
    x,y = map(int,input().split())
    uf.unite(x-1,y-1)
parent = set()
for i in range(n):
    parent.add(uf.find(i))
    p[uf.find(i)] = p[uf.find(i)] | p[i]
    r[uf.find(i)] = r[uf.find(i)] | r[i]

ans = 0
for i in parent:
    ans += len(p[i]) + len(r[i]) - len(p[i] | r[i])
print(ans)


### FIXED CODE ###

class UnionFind:
    def __init__(self, n, p):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

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

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

    uf = UnionFind(n,p)
    for i in range(m):
        x,y = map(int,input().split())
        uf.unite(x-1,y-1)

    ans = 0
    for i,j in enumerate(p):
        ans += uf.same(i, j-1)
    print(ans)
main()
### BUGGY CODE ###

S = input()
mod_bucket = [0] * 2019
mod_bucket[0] += 1

for i in range(len(S)):
    mod = int(S[i:]) % 2019
    mod_bucket[mod] += 1

ans = 0
for mod in mod_bucket:
    ans += int(mod * (mod-1) / 2)
print(ans)


### FIXED CODE ###

S = input()
mod_bucket = [0] * 2019
mod_bucket[0] += 1

_S = S[::-1]
mod = 0
p = 1
for i in range(len(S)):
    mod = (p * int(_S[i]) + mod) % 2019
    mod_bucket[mod] += 1
    p *= 10
    p %= 2019

ans = sum([mod*(mod-1)/2 for mod in mod_bucket])
print(int(ans))
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
left = 0
ans = 1
l = 1
pre = A[0]
right = 1
while left < N-1:
    if pre == -1:
        left += 1
        pre = A[left]
        right += 1
    elif right >= N:
        # N -= 1
        A[left] = -1
        left += 1
        # A.pop(left)
        l = 1
        ans += 1
        right = left+1
        pre = A[left]
    elif pre < A[right]:
        l += 1
        pre = A[right]
        A[right] = -1
        right += 1
    else:
        right += 1
if pre == -1:
    ans -=1
print(ans)


### FIXED CODE ###

import bisect
def LIS():
    L[0] = A[0]
    length = 1
    for i in range(1, N):
        if L[length-1] < A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_left(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

def LISDesc():
    L[0] = A[-1]
    length = 1
    for i in range(N-2, -1, -1):
        if L[length-1] <= A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_right(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

INFTY = 10**13
N = int(input())
A = [int(input()) for i in range(N)]
L = [INFTY for i in range(N)]
ans = LISDesc()
print(ans)
### BUGGY CODE ###

import collections


if __name__ == '__main__':
    n = int(input())
    s = [str(input()) for i in range(n)]

    c = []


    for i in range(n):
        c.append(collections.Counter(s[i]))

    answer = 0
    for i in range(n):
        for j in range(i+1,n):
            if c[i] == c[j]:
                answer += 1
    print(answer)



### FIXED CODE ###

import collections


if __name__ == '__main__':
    n = int(input())
    s = ["".join(sorted(list(input()))) for i in range(n)]

    c = collections.Counter(s)

    answer = 0
    for cnt in c.values():
        answer += cnt*(cnt-1)//2
    print(answer)
### BUGGY CODE ###

S = input()
N = len(S)
table = [1] + [0] * 2020

curr = 0
for i in range(N):
    curr += int(S[N-1-i])*(10**i)
    curr %= 2019
    table[curr] += 1

ans = 0
for i in table:
    ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
table = [1] + [0] * 2020
exp = [1]
for i in range(N):
    exp += [exp[-1]*10 %2019]

curr = 0
for i in range(N):
    curr += int(S[N-1-i])*exp[i]
    curr %= 2019
    table[curr] += 1

ans = 0
for i in table:
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from random import randrange
from bisect import bisect
from time import perf_counter

def resolve():
    tick = perf_counter() + 1.90
    it = map(int, sys.stdin.read().split())
    D = next(it)
    C = [next(it) for i in range(26)]
    S = [[next(it) for i in range(26)] for i in range(D)]
    L = [[-1] for i in range(26)]
    T = [0] * D

    def update(di, qi):
        T1, L1 = T[:], L[:]

        score = 0
        t0 = T[di]
        score += S[di][qi]-S[di][t0]
        T1[di] = qi

        L1[t0] = li = L[t0][:]
        ii = li.index(di)
        la = D if len(li)-1 == ii else li[ii+1]
        score -= C[t0] * (di-li[ii-1])*(la-di)
        li.pop(ii)

        L1[qi] = li = L[qi][:]
        ii = bisect(li, di)
        li.insert(ii, di)
        la = D if len(li)-1 == ii else li[ii+1]
        score += C[qi] * (di-li[ii-1])*(la-di)

        return score, T1, L1

    score = 0
    x = (1+D)*D//2
    for i in range(D):
        score += S[i][0]
        L[0].append(i)

    for i in range(1, 26):
        score -= C[i] * x

    while perf_counter() < tick:
        diff, T1, L1 = update(randrange(0, D), randrange(0, 26))
        if diff > 0:
            score += diff
            T, L = T1, L1

    print(*(i+1 for i in T), sep="\n")

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    D = next(it)
    C = [next(it) for i in range(26)]
    S = [[next(it) for i in range(26)] for i in range(D)]

    ans = []
    for i in range(D):
        ss = S[i]
        di, qi = 0, ss[0]
        for j in range(1, 26):
            if ss[j] > qi:
                di, qi = j, ss[j]
        ans.append(di+1)

    print(*ans, sep="\n")

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

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

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

from bisect import bisect_left


ans = 0

for k in range(29):
    b0 = []
    b1 = []
    b0a = b0.append
    b1a = b1.append
    for i in b: #基数ソート
        if i&(1<<k): b1a(i)
        else: b0a(i)
    b = b0+b1
    mask = (1<<(k+1))-1
    
    aa = [i&mask for i in a]
    bb = [i&mask for i in b]
    
    res = 0
    p1 = 1<<k
    p2 = mask+1
    p3 = p1+p2
    
    for ai in aa:
        if p1-ai<0:
            j1 = 0
        else:
            j1 = bisect_left(bb,p1-ai)

        j2 = bisect_left(bb,p2-ai)
        
        if p3 - ai > bb[-1]:
            j3 = n
        else:
            j3 = bisect_left(bb,p3-ai)
        
        res += j2-j1+n-j3
        #if k < 3: print(ai,p2,res,bb,1,j2,j3,n)
        #print(bb,p2,ai,j1,j2,j3,n,"R",res)    
    ans |= (res&1)<<k
    



print(ans)    









### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

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

from bisect import bisect_left


ans = 0

for k in range(29):
    a0 = []
    a1 = []
    a0a = a0.append
    a1a = a1.append
    
    b0 = []
    b1 = []
    b0a = b0.append
    b1a = b1.append
    for i in a: #基数ソート
        if i&(1<<k): a1a(i)
        else: a0a(i)
    for i in b: #基数ソート
        if i&(1<<k): b1a(i)
        else: b0a(i)
    
    a = a0+a1
    b = b0+b1
    mask = (1<<(k+1))-1
    
    aa = [i&mask for i in a]
    bb = [i&mask for i in b]
    
    res = 0
    p1 = 1<<k
    p2 = mask+1
    p3 = p1+p2

    j1=j2=j3=0    
    for ai in reversed(aa):
        while j1 < n and ai+bb[j1] < p1:
            j1 += 1
        while j2 < n and ai+bb[j2] < p2:
            j2 += 1
        while j3 < n and ai+bb[j3] < p3:
            j3 += 1
        res += j2-j1+n-j3
        #if k < 3: print(ai,p2,res,bb,j1,j2,j3,n)
        #print(bb,p2,ai,j1,j2,j3,n,"R",res)    
    ans |= (res&1)<<k
    



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

def resolve():
    # 整数 1 つ
    # n = int(input())
    # 整数複数個
    k, s = list(map(int, input().split()))
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    # N = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    cnt = 0
    for x in range(k+1):
        for y in range(k+1):
            for z in range(k+1):
                if x + y + z == s:
                    cnt += 1
                    break
            if x + y > s:
                break
        if x > s:
            break

    print(cnt)


resolve()

### FIXED CODE ###

def resolve():
    # 整数 1 つ
    # n = int(input())
    # 整数複数個
    k, s = list(map(int, input().split()))
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    # N = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    cnt = 0
    for x in range(k+1):
        if x == s:
            cnt += 1
            break
        for y in range(k+1):
            c = s - (x + y)
            if c <= k and c >= 0:
                cnt += 1

#            for z in range(k+1):
 #               if x + y + z == s:
  #                  cnt += 1
   #                 break
    print(cnt)

resolve()
### BUGGY CODE ###

n,a,b = map(int, input().split())
M = 10**9 + 7
from math import factorial
from functools import reduce
A = pow(2,n,M) - 1
B = reduce(lambda x, y: x*y, [n-i for i in range(a)]) * pow(factorial(a), M - 2, M) % M
C = reduce(lambda x, y: x*y, [n-i for i in range(b)]) * pow(factorial(b), M - 2, M) % M
print((A-B-C)%M)

### FIXED CODE ###

n,a,b = map(int, input().split())
M = 10**9 + 7
from math import factorial
from functools import reduce
A = pow(2,n,M) - 1

q = r = 1
for i in range(a):
    q = q * (n - i) %  M
for j in range(b):
    r = r * (n - j) %  M

B = q * pow(factorial(a), M - 2, M) % M
C = r * pow(factorial(b), M - 2, M) % M
print((A-B-C)%M)
### BUGGY CODE ###

N = int(input())
A = tuple(map(lambda n: int(n) - 1, input().split()))

if not 0 in A:
    print(-1)
else:
    nf = 0
    for j in range(N+1):
        # jは残す数
        try:
            nf = A[nf:].index(j)
        except ValueError:
            break

    print(N - j)

### FIXED CODE ###

N = int(input())
A = tuple(map(lambda n: int(n) - 1, input().split()))

rem = 0
bk = 0
for a in A:
    if a == rem:
        rem += 1
    else:
        bk += 1

if bk == N:
    print(-1)
else:
    print(bk)
### BUGGY CODE ###

import re
N = int(input())
S = input()
cnt = 0
for i in range(10):
    for j in range(10):
        for h in range(10):
            patrn = r".*" + re.escape(str(i)) + r".*" + re.escape(str(j)) + r".*" + re.escape(str(h)) + r".*"
            repatrn = re.compile(patrn)
            result = repatrn.match(S)
            #result = re.match(patrn, S)
            if result != None:
                cnt += 1
print(cnt)

### FIXED CODE ###

import re
#import time
N = int(input())
S = input()
#start = time.time()
cnt = 0
for i in range(10):
    fir = S.find(str(i))
    if fir == -1:
        continue
    for j in range(10):
        sec = S.find(str(j), fir + 1)
        if sec == -1:
            continue
        for h in range(10):
            thi = S.find(str(h), sec + 1)
            if thi == -1:
                continue
            cnt += 1
print(cnt)
#stop = time.time()
#print(stop - start)
### BUGGY CODE ###

N = int(input())

s = input()

res = 0

for i in range(1000):
    if 99 < i:
        v = str(i)
    elif 9 < i:
        v = '0'+str(i)
    else:
        v = '0'+'0'+str(i)
    
    # ステップ1
    p1 = -1
    for j in range(N-2):
        if s[j] == v[0]:
            p1 = j
            break
    
    if p1 < 0: continue

    # ステップ2
    p2 = -1
    for j in range(p1+1,N-1):
        if s[j] == v[1]:
            p2 = j
            break
    
    if p2 < 0: continue

    # ステップ3
    p3 = -1
    for j in range(p2+1,N):
        if s[j] == v[2]:
            res += 1
            break
print(res)            


### FIXED CODE ###

N = int(input())

s = input()

res = 0

search = [("00"+str(s))[-3:] for s in range(0,1000)]

for v in search:
    tmp = s
    if v[0] in tmp:
        tmp = tmp[tmp.index(v[0])+1:]
    else:
        continue
    if v[1] in tmp:
        tmp = tmp[tmp.index(v[1])+1:]
    else:
        continue
    if v[2] in tmp:
        res += 1
print(res)
### BUGGY CODE ###

INFTY = 1<<30
class MaxHeap():
    def __init__(self, a, h):
        self.a = a
        self.h = h
        
    def parent(self, i):
        return i//2
        
    def left(self, i):
        return 2 * i

    def right(self, i):
        return 2 * i + 1

    def maxHeapify(self, i):
        l = self.left(i)
        r = self.right(i)
        if l <= self.h and self.a[l] > self.a[i]:
            largest = l
        else:
            largest = i
        if r <= self.h and self.a[r] > self.a[largest]:
            largest = r
        if largest != i:
            self.a[i], self.a[largest] = self.a[largest], self.a[i]
            self.maxHeapify(largest)

    def extract(self):
        if self.h < 1:
            return -INFTY
        maxv = self.a[1]
        self.a[1] = self.a[self.h]
        self.h -= 1
        self.maxHeapify(1)
        return maxv
        
    def increaseKey(self, i, k):
        if k < self.a[i]:
            return
        self.a[i] = k
        while i > 1 and self.a[i//2] < self.a[i]:
            self.a[i], self.a[i//2] = self.a[i//2], self.a[i]
            i = i // 2

    def insert(self, k):
        self.h += 1
        self.a[self.h] = -INFTY
        self.increaseKey(self.h, k)

if __name__ == '__main__':
    a = [None] * (2000000 + 1)
    x = MaxHeap(a, 0)
    while True:
        com = input().rstrip()
        if com == "end":
            break
        elif com.startswith("insert"):
            k = int(com.split(" ")[1])
            x.insert(k)
        elif com.startswith("extract"):
            print(x.extract())
    

### FIXED CODE ###

import heapq
import sys

h = []

for com in sys.stdin.readlines():
    if com[0] == "i":
        heapq.heappush(h, -int(com[7:]))
    elif com[1] == "x":
        print(-heapq.heappop(h))
### BUGGY CODE ###

# C - Walk on Multiplication Table
# https://atcoder.jp/contests/abc144/tasks/abc144_c

n = int(input())

comb=[]

# i*j=n となる組み合わせを算出
for i in range(1,n+1):
    for j in range(1,n+1):
         if n == (i*j):
             comb.append((i-1)+(j-1))
# その中で最小のものを出力
print(sorted(comb)[0])


### FIXED CODE ###

# C - Walk on Multiplication Table
# https://atcoder.jp/contests/abc144/tasks/abc144_c

import math

n = int(input())
sqr = int(math.sqrt(n)) + 1
for i in range(sqr, 0, -1):
         if (n % i) == 0:
            print(i + (n//i) - 2)
            exit()
### BUGGY CODE ###

S = input()
N = len(S)
K = int(input())

S1 = {}
for i, s in enumerate(S):
    if not s in S1.keys():
        S1[s] = [i]
    else:
        S1[s].append(i)
alp = sorted(list(S1.keys()))

c = 0
for a in alp:
    aset = set()
    inds = S1[a]
    for d in inds:
        for i in range(N-d+1):
            aset.add(S[d:d+i])
    if len(aset)-1 >= K-c: break
    c += len(aset)-1


while True:
    for i, a in enumerate(aset):
        if i == 0:
            min = a
            continue
        if a < min:
            min = a
    aset.discard(min)
    if min == '': continue
    c += 1
    if c >= K:
        ans = min
        break

print(ans)


### FIXED CODE ###

def main():
    S = input()
    N = len(S)
    K = int(input())

    S1 = {}
    for i, s in enumerate(S):
        if not s in S1.keys():
            S1[s] = [i]
        else:
            S1[s].append(i)
    alp = sorted(list(S1.keys()))

    c = 0
    for a in alp:
        aset = set()
        inds = S1[a]
        for d in inds:
            up = min(N-d+1, K+1)
            for i in range(up):
                aset.add(S[d:d+i])
        L = len(aset)-1
        if L >= K-c:
            break
        c += L

    for _ in range(10):
        M = '何だこれはもうやめてくれよ'
        for a in aset:
            if a < M:
                M = a
        aset.discard(M)
        if M == '':
            continue
        c += 1
        if c >= K:
            ans = M
            break

    print(ans)



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

n=int(input())
a=list(map(int,input().split()))
v=[0]*64
ans=0
mod=1000000007
zero=0
one=0

index=n-1
while index>=0:
	for k in range(64):
		one=v[k]
		zero=n-1-index-one
		if((a[index]&(1<<k))==0):
			ans=(ans+(1<<k)*one)%mod
		else:
			ans=(ans+(1<<k)*zero)%mod
			v[k]=v[k]+1
	index-=1


print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
v=[0]*64
ans=0
mod=1000000007
zero=0
one=0

index=n-1
while index>=0:
	for k in range(61):
		one=v[k]
		zero=n-1-index-one
		tmp=1<<k
		if((a[index]&tmp)==0):
			ans=(ans+tmp*one)
		else:
			ans=(ans+tmp*zero)
			v[k]=v[k]+1
	index-=1

ans=ans%mod
print(ans)
print()
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
count = 0
for i in range(N):
  for j in range(i+1, N):
    max_len = L[i] + L[j] - 1
    left = j+1
    right = N
    while left < right:
      mid = (left + right) // 2
      if L[mid] < max_len:
        left = mid + 1
      elif L[mid] > max_len:
        right = mid
      else:
        while mid < N - 1 and L[mid] == L[mid]:
          mid += 1
          count += mid - j
          break
    else:
      count += right - j - 1
print(count)

### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
count = 0
for i in range(N):
    for j in range(i+1, N):
        max_len = L[i] + L[j]
        count += bisect_left(L, max_len) - j - 1
print(count)
### BUGGY CODE ###

import math


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

ans = []
for i in range(n-1):
  for j in range(i+1, n):
    if a[j] > a[i]:
      res = math.factorial(a[j])//(math.factorial(a[i])*math.factorial(a[j-i]))
      ans.append((res, a[j], a[i]))
#print(max(ans))
print(max(ans)[1], max(ans)[2])

### FIXED CODE ###

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

ans = a[1]
for i in range(1, n-1):
  if abs(a[0]/2 - a[i]) > abs(a[0]/2 - a[i+1]):
    ans = a[i+1]
  else:
    break
print(a[0], ans)
### BUGGY CODE ###

n = int(input())
R = []
max = -10**9
for i in range(n):
    R.append(int(input()))
for i in range(n-1):
    for j in range(i+1, n):
        if R[j] - R[i] > max:
            max = R[j] - R[i]
print(max)



### FIXED CODE ###

max_R = -10**9
for i in range(int(input())):
    if i == 0:
        min_R = int(input())
        continue
    R = int(input())
    if R - min_R > max_R:
        max_R = R - min_R
    if R < min_R:
        min_R = R
print(max_R)
### BUGGY CODE ###

A, B, C, K = input().split(' ')
A = int(A)
B = int(B)
C = int(C)
K = int(K)
while True:
  if A==B==C:
    print(0)
    break

  else:
    for i in range(K):
      a = B + C
      b = A + C
      c = A + B
      A = a
      B = b
      C = c
    if A-B>10**18:
      print('Unfair')
    else:
      print(A-B)

### FIXED CODE ###

A, B, C, K = input().split(' ')
A = int(A)
B = int(B)
C = int(C)
K = int(K)
if K%2==0:
  print(A-B)
else:
  print(B-A)
### BUGGY CODE ###

from operator import mul
from functools import reduce
import bisect

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N = int(input())
A = sorted(list(map(int,input().split())))
maxA = max(A)
A.remove(maxA)
idx = bisect.bisect(A,maxA//2)
if idx == len(A):
  print(maxA,A[-1])
elif idx == 0:
  print(maxA, idx)
else:
  if cmb(maxA,A[idx]) > cmb(maxA,A[idx-1]):
    print(maxA,A[idx])
  else:
    print(maxA,A[idx-1])

### FIXED CODE ###

from operator import mul
from functools import reduce
import bisect

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N = int(input())
A = sorted(list(map(int,input().split())))
maxA = max(A)
A.remove(maxA)
idx = bisect.bisect(A,maxA//2)

if idx == len(A):
  print(maxA,A[-1])
elif idx == 0:
  print(maxA, idx)
else:
  if abs(maxA//2 - A[idx]) > abs(maxA//2 - A[idx-1]):
    print(maxA,A[idx-1])
  else:
    print(maxA,A[idx])
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
#print()
#print("#"*20)
for q in range(Q):
    c=0
    l,r=map(int,input().split())
    for i in range(l-1,r-1):
        #print(S[i:i+2])
        if S[i:i+2]=="AC":
            c+=1
    print(c)



### FIXED CODE ###

N,Q=map(int,input().split())
S=input()

# 最初から数えておく
#C=[1 if S[i:i+2]=='AC' else 0 for i in range(N-1)]
C=[0]*(N+1)
for i in range(N):
    C[i+1]=C[i]+(1 if S[i:i+2]=='AC' else 0)
#print(C)
#exit()

#print()
#print("#"*20)
for q in range(Q):
    l,r=map(int,input().split())
    #print(S[l-1:r].count("AC"))
    #print(sum(C[l-1:r-1]))
    print(C[r-1]-C[l-1])