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

n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(10 ** 9)
    R.append(10 ** 9)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergesort(A, left, right):
    if left+1 < right:
        mid = (left+right)//2
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)

mergesort(s, 0, n)

for i in s:
    a = str(a) + str(i) + ' '
print(a[1:-1])
print(c)


### FIXED CODE ###

import sys
n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergesort(A, left, right):
    if left+1 < right:
        mid = (left+right)//2
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)

mergesort(s, 0, n)

for i in range(n-1):
    print(s[i], end=' ')
print(s[n-1])
print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def main():
    N = int(input().strip())
    l = sorted([int(i) for i in input().strip().split()])
    ans = 0
    uniq = set(l)
    for i in list(uniq):
        divisors = make_divisors(i)
        if l.count(i) > 1:
            continue
        uniq.remove(i)
        for d in divisors:
            if d in uniq:
                break
        else:
            uniq.add(i)
            ans += 1
            continue
        uniq.add(i)
        continue

    return ans


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    l = [int(i) for i in input().strip().split()]
    ans = 0
    m = max(l)
    dp = [0] * (m+1)

    for n in l:
        for j in range(n, m + 1, n):
            dp[j] += 1

    for n in l:
        if dp[n] == 1:
            ans += 1

    return ans


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

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


def calc(a, b):
  while a != 0 and b != 0:
    if a < b:
      b -= a
    else:
      a -= b

  return a if a != 0 else b


def main():
  input()
  a = list(map(int, input().split()))
  p = [a[0], a[1], calc(a[0], a[1])]

  for v in a[2:]:
    for j in range(len(p) - 1):
      p[j] = calc(p[j], v)

    p.append(calc(p[-1], v))

  print(max(p), flush=True)


if __name__ == '__main__':
  main()



### FIXED CODE ###

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


def cd(a, b):
  if a == 1 or b == 1:
    return 1

  while a != 0 and b != 0:
    if a < b:
      b %= a
    else:
      a %= b

  return a if a != 0 else b


def main():
  input()
  prevs = list(map(int, input().split()))
  posts = prevs[::-1]

  for i in range(1, len(prevs)):
    prevs[i] = cd(prevs[i - 1], prevs[i])
    posts[i] = cd(posts[i - 1], posts[i])

  posts = posts[::-1]

  gcd = max(prevs[-2], posts[1])

  for i in range(1, len(prevs) - 1):
    gcd = max(cd(prevs[i - 1], posts[i + 1]), gcd)

  print(gcd, flush=True)


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

A, B, M = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

x = [0] * M
y = [0] * M
c = [0] * M

ans = []

for i in range(M):
    x[i], y[i], c[i] = [int(k) for k in input().split()]
for i in a:
    for j in b:
        ans.append(i + j)

for i in range(M):
    ans.append(a[x[i]-1] + b[y[i]-1] - c[i])

print(min(ans))

### FIXED CODE ###

A, B, M = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

x = [0] * M
y = [0] * M
c = [0] * M

ans = []
ans.append(min(a) + min(b))
for i in range(M):
    x[i], y[i], c[i] = [int(k) for k in input().split()]

for i in range(M):
    ans.append(a[x[i] - 1] + b[y[i] - 1] - c[i])

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

def fun(n):
    ops = 0
    while n:
        pc = format(n, 'b').count('1')
        n %= pc
        ops += 1
    return ops

n = int(input())
xs = input()

sm = int(xs, 2)
pc = xs.count('1')

mp = sm % (pc + 1)
mm = sm % (pc - 1) if pc > 1 else 0

for i, x in enumerate(xs, 1):
    df = 1 if x == '0' else -1
    pci = pc + df
    if pci == 0:
        print(0)
        continue

    #rest = pow(2, n - i, pci)
    rest = (1 << (n - i)) % pci

    if x == '0':
        smi = (mp + rest) % pci
        print(1 + fun(smi))
    else:
        smi = (mm - rest) % pci
        print(1 + fun(smi))


### FIXED CODE ###

from numba import njit

@njit('i8(i8)', cache=True)
def popcount(n):
    a = 0
    while n != 0:
        a += n & 1
        n >>= 1
    return a

@njit('i8(i8)', cache=True)
def fun(n):
    ops = 0
    while n:
        pc = popcount(n)
        n %= pc
        ops += 1
    return ops

n = int(input())
xs = list(map(int, input()))

from functools import reduce
sm = reduce(lambda x,y: x*2+y, xs)
pc = xs.count(1)

# pcの差分を出した後の剰余計算を速くするため、事前にmod pc+1, mod pc-1を計算しておく
mp = sm % (pc + 1)
mm = sm % (pc - 1) if pc > 1 else 0

for i in range(n):
    df = 1 if xs[i] == 0 else -1
    pci = pc + df
    if pci == 0:
        print(0)
        continue

    rest = pow(2, n - i - 1, pci)

    if xs[i] == 0:
        smi = (mp + rest) % pci
        print(1 + fun(smi))
    else:
        smi = (mm - rest) % pci
        print(1 + fun(smi))
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
count = 0
for i in range(N//R+1):
    for j in range(N//G+1):
        for t in range(N//B+1):
            if R*i+G*j+B*t == N:
                count += 1
print(count)

### FIXED CODE ###

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

from collections import deque
import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
load = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    if c > L:
        continue
    load[a-1].append([b-1,c])
    load[b-1].append([a-1,c])
cost =[[float('inf')]*N for i in range(N)]
for i in range(N):
    queue = deque([i])
    cost[i][i] = 0
    while(queue):
        q = queue.popleft()
        gas = cost[i][q]
        for t,c in load[q]:
            if gas//L < (gas+c-1)//L :
                if (gas//L+1)*L+c < cost[i][t]:
                    cost[i][t] = (gas//L+1)*L+c
                    queue.append(t)
            else:
                if gas+c < cost[i][t]:
                    cost[i][t] = gas+c
                    queue.append(t)
Q = int(input())
for i in range(Q):
    s,t = map(int,input().split())
    ans = cost[s-1][t-1]
    if ans == float('inf'):
        print(-1)
    else:
        print((ans-1)//L)
     


### FIXED CODE ###

import sys
imput = sys.stdin.readline
def func(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int,input().split())
road = [[10**10]*N for i in range(N)]
for i in range(N):
    road[i][i] = 0
for i in range(M):
    a,b,c = map(int,input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
road = func(road)
ans = [[10**5]*N for i in range(N)]
for i in range(N):
    for j in range(N):
        if road[i][j] <= L:
            ans[i][j] = 1
ans = func(ans)
for i in range(int(input())):
    a,b = map(int,input().split())
    o = ans[a-1][b-1]
    if o == 10**5:
        print(-1)
    else:
        print(o-1)
### BUGGY CODE ###

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

L, R = map(int, input().split())
ans = set(range(L, R + 1))

for i in range(1, M):
    L, R = map(int, input().split())
    ans &= set(range(L, R + 1))

print(len(ans))

### FIXED CODE ###

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

L = []
R = []

for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

print(max(min(R) - max(L) + 1, 0))
### BUGGY CODE ###

H, W = map(int,input().split())
s = []
rc = [[[None]*W for _ in range(H)] for _ in range(4)]
for _ in range(H):
    s.append(list(input()))
for j in range(H):
    l = s[j]
    for i in range(W):
        if l[i] == "#":
            rc[0][j][i] = 0
        elif i > 0:
            rc[0][j][i] = rc[0][j][i-1] + 1
        else:
            rc[0][j][i] = 1
    for i in range(W-1, -1, -1):
        if l[i] == "#":
            rc[1][j][i] = 0
        elif i < W-1:
            rc[1][j][i] = rc[1][j][i+1] + 1
        else:
            rc[1][j][i] = 1
for i in range(W):
    for j in range(H):
        if s[j][i] == "#":
            rc[2][j][i] = 0
        elif j > 0:
            rc[2][j][i] = rc[2][j-1][i] + 1
        else:
            rc[2][j][i] = 1
    for j in range(H-1, -1, -1):
        if s[j][i] == "#":
            rc[3][j][i] = 0
        elif j < H-1:
            rc[3][j][i] = rc[3][j+1][i] + 1
        else:
            rc[3][j][i] = 1
ans = 0
for j in range(H):
    for i in range(W):
        ans = max(rc[0][j][i]+rc[1][j][i]+rc[2][j][i]+rc[3][j][i]-3, ans)
print(ans)

### FIXED CODE ###

H, W = map(int,input().split())
s = []
rc = [[[None]*W for _ in range(H)] for _ in range(2)]
for _ in range(H):
    s.append(list(input()))
for j in range(H):
    l = s[j]
    for i in range(W):
        if l[i] == "#":
            rc[0][j][i] = 0
        elif i > 0:
            rc[0][j][i] = rc[0][j][i-1] + 1
        else:
            rc[0][j][i] = 1
    for i in range(W-1, -1, -1):
        if l[i] == "#":
            continue
        elif i < W-1:
            rc[0][j][i] = max(rc[0][j][i+1], rc[0][j][i])
for i in range(W):
    for j in range(H):
        if s[j][i] == "#":
            rc[1][j][i] = 0
        elif j > 0:
            rc[1][j][i] = rc[1][j-1][i] + 1
        else:
            rc[1][j][i] = 1
    for j in range(H-1, -1, -1):
        if s[j][i] == "#":
            continue
        elif j < H-1:
            rc[1][j][i] = max(rc[1][j+1][i], rc[1][j][i])
ans = 0
for j in range(H):
    for i in range(W):
        ans = max(rc[0][j][i] + rc[1][j][i] - 1, ans)
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

c = set(['R', 'G', 'B'])
ans = 0
for i in range(n-2):
    d = set(s[i])
    for j in range(i+1, n-1):
        if s[i] != s[j]:
            e = d.copy()
            e.add(s[j])
            p = c-e
            for k in p:
                ans += s[j+1:].count(k)
                if j+j-i < n:
                    if s[j+j-i] == k:
                        ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

ans = s.count('R') * s.count('G') * s.count('B')

for i in range(n-2):
    for j in range(i+1, n-1):
        k = 2*j-i
        if k < n:
            if s[k] != s[i] and s[k] != s[j] and s[i] != s[j]:
                ans -= 1
        else:
            break
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
q = int(input())

mod=1000003

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

#def power(x, y):
#    if   y == 0     : return 1
#    elif y == 1     : return x % mod
#    elif y % 2 == 0 : return power(x, y//2)**2 % mod
#    else            : return power(x, y//2)**2 * x % mod
def power(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

def div(a, b):
    return mul(a, power(b, mod-2))

for j in range(q):
    x,d,n=(int(i) for i in input().split())  
    xd=div(x, d)
    ans=1
    if mod <= xd+n-1:
        ans=0

    for i in range(n):
        ans=mul(ans,xd+i)
    
    print((power(d,n)*ans)%mod)
  



### FIXED CODE ###

import sys
input = sys.stdin.readline
q = int(input())

p=1000003

flist=[1 for i in range(p)]
for i in range(1,p):
    flist[i]=flist[i-1]*i%p

for i in range(q):
  x,d,n=(int(i) for i in input().split())
  if d==0:
    ans=pow(x,n,p)
  else:
    x=x*pow(d,p-2,p)%p    
    if p<=x+n-1:
      ans=0
    else:
      ans=pow(d,n,p)*flist[x+n-1]*pow(flist[x-1],p-2,p)%p
  print(ans%p)
### BUGGY CODE ###

n = int(input())

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

res = 1

for i in range(n):
    res *= a[i]


if res > 10**18:
    print(-1)
else:
    print(res)


### FIXED CODE ###

n = int(input())

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

res = 1

if 0 in a:
    print(0)
else:
    for i in range(n):
        res *= a[i]

        if a[i] == 0:
            break
        if res > 10**18:
            print(-1)
            break


    if res > 10**18:
        pass
    else:
        print(res)
### BUGGY CODE ###

n = int(input())
s = input()

S = []
for i in s:
    S.append(i)

test = ['W' for _ in range(n)]

ans = 100100100
# i番目の人がリーダーの時
for i in range(n):
    # iより西の人は東を向き、iより東の人は西を向くべき
    for j in range(i):
        test[j] = 'E'
    test[i] = S[i]

    # コストを算出
    cost = 0
    for k in range(n):
        if S[k] != test[k]:
            cost += 1
    # ansを更新
    ans = min(ans, cost)

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
S = []
for i in s:
    S.append(i)

w = [0,]
for i in range(1, n):
    if S[i-1] == 'W':
        w.append(w[i-1] + 1)
    else:
        w.append(w[i-1])

e = [0 for _ in range(n)]
for i in range(n-2, -1, -1):
    if S[i+1] == 'E':
        e[i] = e[i+1] + 1
    else:
        e[i] = e[i+1]

ans = 100100100100
for i in range(n):
    cost = w[i] + e[i]
    ans = min(ans, cost)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

n, m=map(int, input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]
g=[list() for i in range(1+n)]
#print(g)

par=[i for i in range(n)]
cnt_con=[1 for i in range(n)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
def connect(x,y):
    #par[x]=root(x)
    #par[y]=root(y)
    if root(x)==root(y):
        0
    else:
        cnt_con[root(y)]+=cnt_con[root(x)]
        par[root(x)]=root(y)      
    return

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


tmp=int(n*(n-1)/2)
ans=[0]*m
ans[-1]=tmp
#ans[0]=0
#print('a,b=',a,b)
for i in range(m-1,-1,-1):
    ans[i]=tmp
    if root(a[i])==root(b[i]):
        0
    else:
        tmp-=cnt_con[root(a[i])]*cnt_con[root(b[i])]
    connect(a[i],b[i])
    #print('i,tmp',i,(a[i],b[i]),ans[i],tmp,par,cnt_con)
    

    
for i in range(m):
    print(ans[i])



### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

n, m=map(int, input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]
g=[list() for i in range(1+n)]
#print(g)

par=[i for i in range(n)]
cnt_con=[1 for i in range(n)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
def connect(x,y):
    #par[x]=root(x)
    #par[y]=root(y)
    if root(x)==root(y):
        0
    else:
        cnt_con[root(y)]+=cnt_con[root(x)]
        par[root(x)]=root(y)      
    return

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


tmp=int(n*(n-1)/2)
ans=[0]*m
ans[-1]=tmp
#ans[0]=0
#print('a,b=',a,b)
for i in range(m-1,-1,-1):
    ans[i]=tmp
    if root(a[i])==root(b[i]):
        0
    else:
        tmp-=cnt_con[root(a[i])]*cnt_con[root(b[i])]
    connect(a[i],b[i])
    #print('i,tmp',i,(a[i],b[i]),ans[i],tmp,par,cnt_con)
    

    
for i in range(m):
    print(ans[i])
### BUGGY CODE ###

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

sums = []

for i in range(n):
    sums +=  [sum(a[i:j+1]) for j in range(i, n)]

print(sums.count(0))

### FIXED CODE ###

from collections import Counter

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

ans = 0

b = [0]
for i in range(n):
	b.append(b[i] + a[i])

c = Counter(b)

for value in c.values():
	ans += value * (value - 1) // 2
    
print(ans)
### BUGGY CODE ###

import itertools

K, = map(int, input().split())
A = tuple(map(int, input().split()))

result = []
for i in itertools.count(1):
  now_i = i
  for a in A:
    now_i = (now_i // a) * a
  if now_i == 2:
    result.append(i)
  if now_i > 2:
    break

if result:
  print(result[0], result[-1])
else:
  print(-1)

### FIXED CODE ###

from pprint import pprint as pp
import collections
import math
import itertools

K, = map(int, input().split())
A = tuple(map(int, input().split()))

old_a = A[-1]
x_max = 2 // A[-1]
x_min = 2 // A[-1]
for a in reversed(A):
  #pp((a, old_a, x_min, x_max))
  if a >= (old_a * (x_max +1)):
    x_max = -1
    break
  x_max = (old_a * (x_max+1)-1) // a
  x_min = math.ceil(old_a * x_min / a)
  if x_max < x_min:
    x_max = -1
    break
  old_a = a
#pp((old_a, x_min, x_max))
if x_max == -1:
  print(-1)
else:
  print(old_a * x_min, (old_a * (x_max+1))-1)
### BUGGY CODE ###

from sys import stdin

n,m = map(int, input().split())
a = list(map(int,input().split()))
for i in range(m):
    a.sort(reverse=True)
    a[0] = a[0]//2

print(sum(a))

### FIXED CODE ###

from sys import stdin
import heapq

n,m = map(int, input().split())
a = [int(x)*(-1) for x in stdin.readline().rstrip().split()]
heapq.heapify(a)

for i in range(m):
    temp = (-1)*heapq.heappop(a)//2
    heapq.heappush(a,temp*(-1))

print(sum(a)*(-1))
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[0]*n
for _ in range(q):
    a[int(input())-1] += 1
for i in a:
    if (sum(a)-i)>=k:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[0]*n
for _ in range(q):
    a[int(input())-1] += 1
c = sum(a)
for i in a:
    if (c-i)>=k:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

n,q = list(map(int,input().split()))
s = list(input())
num = list()
check = [0]*n
for i in range(0,n-1):
    if s[i] == "A" and s[i+1] == "C":
        check[i] = 1
for i in range(0,q):
    num.append(list(map(int,input().split())))
    print(len([k for k in range(num[i][0]-1,num[i][1]-1) if check[k] == 1]))

### FIXED CODE ###

n,q = list(map(int,input().split()))
s = list(input())
num = list()
check = [0]*n
for i in range(1,n):
        if s[i-1] == "A" and s[i] == "C":
                check[i] = check[i-1]+1
        else:
                check[i] = check[i-1]
ans = 0
for i in range(0,q):
        num = list(map(int,input().split()))
        ans = check[num[1]-1]-check[num[0]-1]
        print(ans)
### BUGGY CODE ###

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

for i in range(N[1]):
    A[A.index(max(A))] = int(max(A) / 2)

print(sum(A))

### FIXED CODE ###

import heapq

N = list(map(int, (input().split(' '))))
A = list(map(lambda x: x*(-1), map(int, (input().split(' ')))))

heapq.heapify(A)
for i in range(N[1]):
    heapq.heappush(A, int(heapq.heappop(A) / 2))

print(-sum(A))
### BUGGY CODE ###

import heapq
import sys
from itertools import product
X, Y, Z, K = [int(i) for i in sys.stdin.readline().split()]
A_ls = [int(i) for i in sys.stdin.readline().split()]
B_ls = [int(i) for i in sys.stdin.readline().split()]
C_ls = [int(i) for i in sys.stdin.readline().split()]
_sum_ls = []
for a, b, c in product(A_ls, B_ls, C_ls):
    _sum_ls.append(- (a + b + c))
heapq.heapify(_sum_ls)
for i in range(K):
    k = heapq.heappop(_sum_ls)
    print(-k)

### FIXED CODE ###

import heapq
import sys
from itertools import product
X, Y, Z, K = [int(i) for i in sys.stdin.readline().split()]
A_ls = [int(i) for i in sys.stdin.readline().split()]
B_ls = [int(i) for i in sys.stdin.readline().split()]
C_ls = [int(i) for i in sys.stdin.readline().split()]
A_ls.sort(reverse=True)
B_ls.sort(reverse=True)
C_ls.sort(reverse=True)
_sum_ls = [(-(A_ls[0] + B_ls[0] + C_ls[0]), 0, 0, 0)]
heapq.heapify(_sum_ls)
for i in range(K):
    score, a, b, c = heapq.heappop(_sum_ls)
    print(- score)
    if len(A_ls) > a+1:
        cand = (- (A_ls[a+1] + B_ls[b] + C_ls[c]), a+1, b, c)
        if not cand in _sum_ls:
            heapq.heappush(_sum_ls, cand)
    if len(B_ls) > b+1:
        cand = (- (A_ls[a] + B_ls[b+ 1] + C_ls[c]), a, b+1, c)
        if not cand in _sum_ls:
            heapq.heappush(_sum_ls, cand)
    if len(C_ls) > c+1:
        cand = (- (A_ls[a] + B_ls[b] + C_ls[c+1]), a, b, c+1)
        if not cand in _sum_ls:
            heapq.heappush(_sum_ls, cand)
### BUGGY CODE ###

from bisect import bisect_left
N=int(input())
ll=list(map(int,input().split()))
ll.sort()
ans=0
for i in range(N):
    for j in range(i+1,N):
        delta=bisect_left(ll,ll[i]+ll[j],lo=j)-j-1
        if delta>0:
            ans+=delta
        #print(i,j,delta)
print(ans)

### FIXED CODE ###

from bisect import bisect_left
N=int(input())
ll=list(map(int,input().split()))
ll.sort()
ans=0
for i in range(N):
    for j in range(i+1,N):
        if j==i+1:
            delta=bisect_left(ll,ll[i]+ll[i+1],lo=i+1)-i-2
            if delta>0:
                ans+=delta
            in_b=delta+i+1+1
        else:
            if in_b!=N:
                delta=bisect_left(ll,ll[i]+ll[j],lo=in_b)-j-1
            else:
                delta=N-j-1
            if delta>0:
                ans+=delta
            in_b=delta+j+1
print(ans)
### BUGGY CODE ###

N, Q = input().split()
S = input()
for i in range(int(Q)):
    l, r = (int(x) for x in input().split())
    sub_S = S[l-1:r]
    count = 0
    for j in range(len(sub_S)-1):
        if 'AC' == sub_S[j:j+2]:
            count += 1
    print(count)

### FIXED CODE ###

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

AC_appearance = [0] * len(S)
counter = 0
for i in range(1, len(S)):
    if S[i-1] == 'A' and S[i] == 'C':
        counter += 1
    AC_appearance[i] = counter 

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