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

class SegmentTree:
    _op = None
    _e = None
    _size = None
    _offset = None
    _data = None

    def __init__(self, size, op, e):
        self._op = op
        self._e = e
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def build(self, iterable):
        op = self._op
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def update(self, index, value):
        op = self._op
        data = self._data
        i = self._offset + index
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        op = self._op
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = self._e
        for v in it:
            result = op(result, v)
        return result


N, K, *A = map(int, open(0).read().split())
st = SegmentTree(300000 + 1, max, 0)

for a in A:
    st.update(a, st.query(max(a - K, 0), min(a + K + 1, 300000 + 1)) + 1)

print(st.query(0, 300000 + 1))


### FIXED CODE ###

class SegmentTree:
    _op = None
    _e = None
    _size = None
    _offset = None
    _data = None

    def __init__(self, size, op, e):
        self._op = op
        self._e = e
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def build(self, iterable):
        op = self._op
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def update(self, index, value):
        op = self._op
        data = self._data
        i = self._offset + index
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        op = self._op
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = self._e
        for v in it:
            result = op(result, v)
        return result


N, K, *A = map(int, open(0).read().split())
st = SegmentTree(300000 + 1, max, 0)

for a in A:
    st.update(a, st.query(max(a - K, 0), min(a + K + 1, 300000 + 1)) + 1)

print(st.query(0, 300000 + 1))
### BUGGY CODE ###

N = int(input())
A = list(input().split())
B = [int(a) for a in A]
x = 10**9+7
summation = sum((B[i] * (sum(B[j] for j in range(i+1,N)) % x)) % x for i in range(N-1)) % x
print(summation % x)

### FIXED CODE ###

N = int(input())
A = list(input().split())
B = [int(a) for a in A]
x = 10**9+7
summation1 = sum(B) ** 2
summation2 = sum(b ** 2 for b in B)
summation = ((summation1 - summation2) // 2) % x
print(summation)
### BUGGY CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
p, q, r = cnt[1], cnt[2], cnt[3]


dp = [[[0] * (r + 1) for _ in range(r + q + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0

for k in range(r + 1):
    for j in range(r + q + 1):
        for i in range(n + 1):
            if i != 0:
                dp[i][j][k] += dp[i - 1][j][k] * i / (i + j + k)
            if (j != 0) and (i != n):
                dp[i][j][k] += dp[i + 1][j - 1][k] * j / (i + j + k)
            if (k != 0) and (j != r + q):
                dp[i][j][k] += dp[i][j + 1][k - 1] * k / (i + j + k)
            if (i + j + k) != 0:
                dp[i][j][k] += n / (i + j + k)

print(dp[p][q][r])


### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
a = [0,0,0]
for x in LI():
    a[x-1] += 1
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(a[2]+1):
    for j in range(a[1]+a[2]+1):
        for i in range(N+1):
            if not (0 < i+j+k <= N): continue
            x = 0.0
            if i > 0: x += dp[i-1][j][k] * (i/N)
            if j > 0: x += dp[i+1][j-1][k] * (j/N)
            if k > 0: x += dp[i][j+1][k-1] * (k/N)
            x += 1.0
            x *= N / (i+j+k)
            dp[i][j][k] = x
print(dp[a[0]][a[1]][a[2]])
### BUGGY CODE ###

n=int(input())
l=[]
for i in range(n):
    l.append(int(input()))
for i in range(n):
    tmp=0
    b=[False for x in range(n)]
    b[i]=True
    for j in range(n):
        if(b[j]==False and l[j]>tmp):
            tmp=l[j]
    print(tmp)



### FIXED CODE ###

n=int(input())
l=[]
for i in range(n):
    l.append(int(input()))
# print(l)
x=[]
for i in range(n):
    x.append(l[i])
x.sort()
for i in range(n):
    if(l[i]!=x[n-1]):
     
        print(x[n-1])
    else:

        print(x[n-2])
### BUGGY CODE ###

N=int(input())
ans=0
for i in range(N):
    ans+=i
print(ans)

### FIXED CODE ###

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

q=int(input())
A=[]
b=0
def f(A,b,n):
  res=0
  for a in A:
    res+=abs(a-n)
  return res+b
for _ in range(q):
  L=[int(i) for i in input().split()]
  if L[0]==1:
    A.append(L[1])
    b+=L[2]
  else:
    A.sort()
    n=A[(len(A)-1)//2]
    print(n,f(A,b,n))

### FIXED CODE ###

from heapq import heappop
from heapq import heappush
q=int(input())
L,R=[],[]
b_sum=0
l_sum,r_sum=0,0
count=0
mid=0
for _ in range(q):
  
  Q=list(map(int,input().split()))
  if Q[0]==1:
    a,b=Q[1],Q[2]
    count+=1
    b_sum+=b
    if count==1:
      mid=a
    elif count%2==0:
      if a<=mid:
        heappush(L,-a)
        l_sum+=a
        heappush(R,mid)
        r_sum+=mid
      else:
        heappush(L,-mid)
        l_sum+=mid
        heappush(R,a)
        r_sum+=a
    else:
      l,r=-heappop(L),heappop(R)
      if a<l:
        heappush(L,-a)
        l_sum+=a-l
        mid=l
        heappush(R,r)
      elif r<a:
        heappush(L,-l)
        mid=r
        heappush(R,a)
        r_sum+=a-r
      else:
        heappush(L,-l)
        mid=a
        heappush(R,r)

  else:
    if count%2==1:
      print(mid,r_sum-l_sum+b_sum)
    else:
      l=-heappop(L)
      print(l,r_sum-l_sum+b_sum)
      heappush(L,-l)
### BUGGY CODE ###

N = int(input())
ans = sum(range(N))
print(ans)

### FIXED CODE ###

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

import sys
sys.setrecursionlimit(4100000)

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

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return graph_g[s]

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        dfs(edge, graph_cnt)


for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)

for i in range(K):
    C, D = map(int, input().split())
    block[C-1].append(D-1)
    block[D-1].append(C-1)

for i in range(N):
    dfs(i, None)

group_to_idx = [set() for i in range(graph_cnt+1)]
if len(group_to_idx) != 0:
    for i in range(N):
        group_to_idx[graph_g[i]].add(i)

ret = []
for i in range(N):
    cand = len(group_to_idx[graph_g[i]])
    fri = len(to[i])
    tmp_block = len(group_to_idx[graph_g[i]] & set(block[i]))

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)

from collections import Counter

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

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return 0

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        if graph_g[edge] == None:
            dfs(edge, graph_cnt)


for i in range(M):
    A, B = map(int, input().split())
    to[A-1].append(B-1)
    to[B-1].append(A-1)

for i in range(N):
    if is_visited[i]:
        continue
    dfs(i, None)

for i in range(K):
    C, D = map(int, input().split())
    if graph_g[C-1] == graph_g[D-1]:
        block[C-1].append(D-1)
        block[D-1].append(C-1)

ct = Counter(graph_g)

ret = []
for i in range(N):
    cand = ct[graph_g[i]]
    fri = len(to[i])
    tmp_block = len(block[i])

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)
### BUGGY CODE ###

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

for i in range(Q):
  l, r = map(int, input().split())
  deleted = S[l-1:r]
  print(deleted.count('AC'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N+1)

for i in range(1, N+1):
  t[i] = t[i-1] + (1 if S[i-1:i+1] == 'AC' else 0)
  
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

import sys
n, y = (int(_) for _ in input().split())

for i in range(0,n+1):
    for j in range(0,n+1-i):
        for k in range(0,n+1-i-j):
            if(i+j+k == n):
                if(10000*i+5000*j+1000*k == y):
                    print(i,j,k)
                    sys.exit()
                    
print('-1 -1 -1')

### FIXED CODE ###

## ABC 085C
## C - Otoshidama

import sys
n, y = (int(_) for _ in input().split())

for i in range(0,n+1):
    for j in range(0,n+1-i):
        if(10000*i+5000*j+1000*(n-i-j) == y):
            print(i,j,n-i-j)
            sys.exit()
                    
print('-1 -1 -1')
### BUGGY CODE ###

import numpy as np
N, M, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [0] + list(map(int, input().split()))

csA = np.cumsum(A)
csB = np.cumsum(B)

if csA[-1] + csB[-1] <= K:
    print(N+M)

else:
    
    ans = 0
               
    for i in range(N+1):
        wa = csA[i]
        numA = i
        if wa <= K:
            for j in range(M+1):
                numB = j
                wa += csB[j]
                if wa > K:
                    if numA + numB - 1 > ans:
                        ans = numA + numB - 1
                    break
                else:
                    wa = csA[i]
        else:
            break

    print(ans)

### FIXED CODE ###

import numpy as np
N, M, K = map(int, input().split())
A = np.cumsum([0] + list(map(int, input().split())))
B = np.cumsum([0] + list(map(int, input().split())))
ans = 0
j = M
for i in range(N+1):
  if A[i] > K:
    break
  while A[i] + B[j] > K:
    j -= 1
  ans = max(ans,i+j)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p = [int(x) for x in input().split()]

l = 0
r = k

result = 0.0
while r != len(p)+1:
  this_res = 0.0
  # 期待値の計算
  for pi in p[l:r]:
    this_res += pi / 2 + 1/2
  result = max(result, this_res)
  l += 1
  r += 1

print(result)

### FIXED CODE ###

from itertools import accumulate
n, k = map(int, input().split())
p = list(map(int, input().split()))

pp = [0] + list(accumulate(p))

m = 0
for i in range(n - k + 1):
  m = max(m,pp[i + k] - pp[i])
print((m+k)/2)
### BUGGY CODE ###

import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,sys.stdin.readline().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if time.time() - start_time > 1.7:
        return # gori~~~
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')

### FIXED CODE ###

import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,sys.stdin.readline().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if time.time() - start_time > 1.8:
        # gori~~~
        print('No')
        exit()
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')
### BUGGY CODE ###

n=int(input())
tot=0
while(n>0):
    dig=n%10
    tot=tot+dig
    n=n//10

if tot %9==0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

k=sum(map(int, str(input())))
if k%9==0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    #d = [[10 ** 12] * w for i in range(h)]
    d = []
    for i in range(h):
        d.append([10 ** 12] * w)

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]

d = [[False] * w for i in range(h)]
ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if maze[gx][gy] == ".":
                        if d[gx][gy]:
                            continue
                        ans = max(ans, bfs())
            d[sx][sy] = True

print(ans)


### FIXED CODE ###

from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    #d = [[10 ** 12] * w for i in range(h)]
    d = []
    for i in range(h):
        d.append([10 ** 12] * w)

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]

count = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            count += 1
if count == 400:
    print(38)
    exit()

ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if sx == gx and sy == gy:
                        continue
                    if maze[gx][gy] == ".":
                        ans = max(ans, bfs())

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

n,m=map(int,input().split())
a=list(map(int,input().split()))
d=[]
for i in range(m):
    bi,ci=map(int,input().split())
    for ii in range(bi):
        d.append(ci)
        
a.sort()
d.sort(reverse=True)

lend=len(d)
for i in range(n):
    if lend<=i:
        break
    if a[i]<d[i]:
        a[i]=d[i]
    else:
        break
    
print(sum(a))

### FIXED CODE ###

import sys
from bisect import bisect_left,bisect,bisect_right

icase=0
if icase==0:
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    d=[]
    cb=[[0]*2 for i in range(m)]
    for i in range(m):
        bi,ci=map(int,input().split())
        cb[i]=[ci,bi]
elif icase==1:
    n,m=3,2
    a=[1, 4, 5]
    cb=[[5, 1], [3, 2]]
elif icase==3:
    n,m=3,2
    a=[100, 100, 100]
    cb=[[99, 3], [99, 3]]
elif icase==2:
    n,m=10,3
    a=[1, 4, 5, 5, 7, 8, 13, 33, 52, 100]
    cb=[[30, 4], [10, 3], [4, 1]]
elif icase==4:
    n,m=11,3
    a=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    cb=[[1000000000, 4], [1000000000, 3], [1000000000, 3]]
elif icase==5:
    f=open(r"C:\Users\nishi\999atcoder\ABCD040-151\ABC127D\testcase_13_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    ll=f.readline()
    a=list(map(int,ll.split()))
    d=[]
    cb=[[0]*2 for i in range(m)]
    for i in range(m):
        ll=f.readline()
        bi,ci=map(int,ll.split())
        cb[i]=[ci,bi]
    f.close()
    ans=99913215738299
elif icase==6:
    f=open(r"C:\Users\nishi\999atcoder\ABCD040-151\ABC127D\testcase_12_in.dat")
    ll=f.readline()
    n,m=map(int,ll.split())
    ll=f.readline()
    a=list(map(int,ll.split()))
    d=[]
    cb=[[0]*2 for i in range(m)]
    for i in range(m):
        ll=f.readline()
        bi,ci=map(int,ll.split())
        cb[i]=[ci,bi]
    f.close()
    ans=95821339675952

a.sort()
cb.sort(reverse=True)

if cb[0][0]<=a[0]:
    print(sum(a))
    sys.exit()
    
asum=0
isum=0
isumm=0
for i in range(m):
    isum+=cb[i][1]
    if isum>n:
        if a[-1]<=cb[i][0]:
#        print("A",i)
            asum+=cb[i][0]*(n-isumm)
            print(asum)
            sys.exit()
#    isum=min(isum,n)
#    print(i,isum,a[isum-1])
        else:
#        print("C",i)
            ii=bisect_right(a,cb[i][0])
            asum+=cb[i][0]*(ii-isumm)
#        print(ii,isumm,asum)
#        asum+=sum(a[ii:isum])
            asum+=sum(a[ii:])
            print(asum)
            sys.exit()
    if a[isum-1]<=cb[i][0]:
        asum+=cb[i][0]*cb[i][1]
#        asum+=cb[i][0]*(isum-isumm)
#        print("B",i,isum,asum)
        isumm=isum
        continue
    else:
#        print("C",i)
        ii=bisect_right(a,cb[i][0])
        asum+=cb[i][0]*(ii-isumm)
#        print(ii,isumm,asum)
#        asum+=sum(a[ii:isum])
        asum+=sum(a[ii:])
        print(asum)
        sys.exit()
#        isumm=isum
#        break
    isumm=isum
    
#if isumm<n:
asum+=sum(a[isumm:])
        
print(asum)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from operator import mul
from functools import reduce

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 = []
for i in range(N):
  temp = input()
  temp = list(temp)
  temp.sort()
  a.append("".join(temp))

count = 0
for s in set(a):
  temp = a.count(s)
  if temp >= 2:
    count += cmb(temp,2)

print(int(count))

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
dic = {}
count = 0
for i in range(N):
  temp = "".join(sorted(input()))
  if temp in dic:
    count += dic[temp]
    dic[temp] += 1
  else:
    dic[temp] = 1

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

# -*- coding: utf-8 -*-
import sys


def get_num():
    return int(input())


def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())

n, q = get_numbers()
s = input()


ans = list()
for i in range(q):
    l, r = get_numbers()
    ans.append(s[l - 1:r].count('AC'))

for a in ans:
    print(a)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys


def get_num():
    return int(input())


def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())

n, q = get_numbers()
s = input()

dp = [0 for _ in range(n + 1)]
for i in range(1, n):
    dp[i + 1] = dp[i]
    if s[i - 1:i + 1] == 'AC':
        dp[i + 1] += 1

ans = list()
for i in range(q):
    l, r = get_numbers()
    ans.append(dp[r] - dp[l])

for a in ans:
    print(a)
### BUGGY CODE ###

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

import math

ans=0
if N < B:
  end = N + 1
else:
  end = B

for x in range(1,end):
  tmp=math.floor(A*x/B) - A * math.floor(x/B)
  if tmp > ans:
    ans = tmp

for x in range(B-1,N,B):
  tmp=math.floor(A*x/B) - A * math.floor(x/B)
  if tmp > ans:
    ans = tmp
  
print(tmp)


### FIXED CODE ###

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

import math

ans=0
if N < B:
  end = N
else:
  end = B -1

x = end
tmp=math.floor(A*x/B) - A * math.floor(x/B)
  
print(tmp)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Aug 18 21:19:43 2019
ABC138D
@author: maezawa
"""

n, q = list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    ai, bi = list(map(int, input().split()))
    graph[ai].append(bi)
    graph[bi].append(ai)
    
parent = [[] for _ in range(n+1)]
child = [[] for _ in range(n+1)]
current = 1
while current <= n:
    for j in graph[current]:
        if current in child[j]:
            continue
        child[current].append(j)
    current += 1
#print(child)
parray = [-1]*(n+1)
parray[1] = 0
for i in range(1,n+1):
    for j in child[i]:
        parray[j] = i
#print(parray)
tpoint = [0]*(n+1)
for i in range(q):
    pi, xi = list(map(int, input().split()))
    tpoint[pi] += xi
for i in range(1, n+1):
    pi = 0
    j = i
    while True:
        pi += tpoint[j]
        if parray[j] == -1:
            break
        j = parray[j]
    print(pi)
    

### FIXED CODE ###

n, q = list(map(int, input().split()))
nodes = [[] for _ in range(n)]
for _ in range(n-1):
    ai, bi = list(map(int, input().split()))
    nodes[ai-1].append(bi-1)
    nodes[bi-1].append(ai-1)
    
cnts = [0]*n
for _ in range(q):
    pi, xi = list(map(int, input().split()))
    cnts[pi-1] += xi
    
stack = []
visited = set()
stack.append(0)
while stack:
    current = stack.pop(-1)
    visited.add(current)
    for j in nodes[current]:
        if j in visited:
            continue
        cnts[j] += cnts[current]
        stack.append(j)
        
print(*cnts)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
t = 0
for i in range(len(a)):
    for j in range(i+1, len(a)):
        t += a[i]*a[j]
print(t%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
t = 0
r = 0
mod = 10**9+7
for i in range(n-1, 0, -1):
    r += a[i]
    t += a[i-1]*r
print(t%mod)
### BUGGY CODE ###

def main():
  from fractions import gcd
  mod = 10**9 + 7
  N = int(input())
  A = list(map(int, input().split()))

  lcm = A[0]
  for i in range(1, N):
    lcm = (lcm*A[i]) // gcd(lcm, A[i])

  ans = 0
  for i in range(N):
    ans += lcm // A[i]
  print(ans%mod)
main()

### FIXED CODE ###

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)