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

import math

def nCr(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

def wantp(n):

    nown = n
    Q = []
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q:
                p[i] = nown

            return nown


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

AB = []
for i in range(M):

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

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = []
c = []
rank = [1] * N
up2 = set([])

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M):

    a = AB[i][0]
    b = AB[i][1]

    ap = wantp(a)
    bp = wantp(b)

    if ap != bp:

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

            up2 = up2 - set([bp])
            up2 = up2 | set([ap])

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

        else:

            p[ap] = bp
            c[bp] += c[ap]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

            rank[bp] += 1

    now = 0

    for j in up2:

        now += nCr(c[j],2)

    ans.append(nCr(N,2) - now)

ans.reverse()

for i in range(M):
    print (ans[i+1])


### FIXED CODE ###

import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def nC2(n):
    if n-2 >= 0:
        return (n*(n-1)) // 2
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    cnt = 0
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
                cnt += 1

            break

        cnt += 1

        if cnt > 10:
            print (n,nown,p[nown])

    return nown


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

AB = []
for i in range(M):

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

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    #if i % 1000 == 0 or i > 25000:
        #print (i)

    #if i > 25000 : print ("A")

    a = AB[i][0]
    b = AB[i][1]

    #if i > 25000 : print ("B") 

    ap = wantp(a)
    bp = wantp(b)

    #if i > 25000 : print ("C")

    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nC2(c[ap]) + nC2(c[bp]) - nC2(c[ap]+c[bp])

        #if i > 25000 : print ("D")

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

        #if i > 25000 : print ("E")

    ans.append(now)
    #if i > 25000 : print ("F")
    #print (now,p)

#print ("test")
ans.reverse()

for i in range(M):
    print (ans[i+1])
### BUGGY CODE ###

a = int(input())
b = []
for i in range(a):
  if a%(i+1)==0:
    b.append(i+1)
wa = 100000000000
for i in range(len(b)):
    wa1 = b[i] + b[len(b)-i-1]
    if wa >= wa1:
      wa = wa1
if len(b)%2==1:
  wa1 = b[int(len(b)/2) + 1] * 2
  if wa >= wa1:
    wa = wa1
print(wa-2)

### FIXED CODE ###

import math

def FindAllDivisors(x):
    divList = []
    y = 1
    while y <= math.sqrt(x):
        if x % y == 0:
            divList.append(y)
            divList.append(int(x / y))
        y += 1
    return divList

n = int(input())
a = FindAllDivisors(n)

b = 10000000000
for i in range(len(a)):
  if i%2==1:
    continue
  else:
    bb = a[i]+a[i+1]
    if b >= bb:
      b = bb

print(bb-2)
### BUGGY CODE ###

def main():
  N=int(input())
  P=list(map(int,input().split()))
  sFlag=True
  i=0
  sumCount=0
  for i in range(N):
    Pi=P[i]
    for j in range(0,i+1):
      Pj=P[j]
      if(Pi>Pj):
        break
      if(j==i):
        sumCount=sumCount+1
  print(sumCount)
if __name__ == '__main__':
  main()

### FIXED CODE ###

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

num = p[0]
ans = 1

for i in range(1, n):
    if num >= p[i]:
        ans += 1
        num = p[i]

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

# coding: utf-8
import sys

N, W = map(int, sys.stdin.buffer.readline().split())
w, v = [0 for _ in range(N+10)], [0 for _ in range(N+10)]

for i in range(1, N+1):
    w[i], v[i] = map(int, sys.stdin.buffer.readline().split())
   
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

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

# for i in range(N+1):
#     print(dp[i])

print(dp[N][W])

### FIXED CODE ###

def main():
    N, W = map(int, input().split())
 
    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))
 
 
main()
### BUGGY CODE ###

s = input()
q = int(input())
array = [list(map(str, input().split())) for i in range(q)]
#print(array)
for i in range(q):
    if array[i][0] == "1":
        s = s[::-1]
    elif array[i][1] == "1":
        s = array[i][2] + s
    elif array[i][1] == "2":
        s = s + array[i][2]
print(s)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
array = [list(map(str, input().split())) for i in range(q)]
#print(array)
d = deque(s)
reverse = 1
for i in range(q):
    if array[i][0] == "1":
        reverse *= -1
    elif (array[i][1] == "1") and (reverse == 1):
        d.appendleft(array[i][2])
    elif (array[i][1] == "1") and (reverse == -1):
        d.append(array[i][2])
    elif (array[i][1] == "2") and (reverse == 1):
        d.append(array[i][2])
    elif (array[i][1] == "2") and (reverse == -1):
        d.appendleft(array[i][2])

if reverse == -1:
    d.reverse()

d_str = "".join(list(d))
print(d_str)
### BUGGY CODE ###

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

s = 0

for i in range(N):
    for k in range(i+1, N):
        s += a[i] * a[k]

print(s % (10 ** 9 + 7))

### FIXED CODE ###

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

s = 0
r = [0] * N
r[0] = a[0]

for i in range(1, N):
    r[i] = r[i-1] + a[i]

for i in range(N-1):
    s += a[i] * (r[N-1] - r[i])

print(s % (10 ** 9 + 7))
### BUGGY CODE ###

from bisect import bisect_left
H,W = map(int,input().split())
S = []
for i in range(H):
    s = input()
    S.append([x for x in s])

S_t = list(map(list, zip(*S)))

S_h = [[] for i in range(H)]
S_w = [[] for i in range(W)]

for x in range(W):
    for y in range(H):
        if S[y][x] == '#':
            S_h[y].append(x)
            S_w[x].append(y)

ans = 0
for x in range(W):
    for y in range(H):
        if S[y][x] == '.':
            c = 1
            if len(S_w[x]) == 0:
                c += H-1
            else:
                i = bisect_left(S_w[x],y)
                if i == 0:
                    c += S_w[x][0]-1
                elif i == len(S_w[x]):
                    c += H-S_w[x][-1]-2
                else:
                    c += S_w[x][i]-S_w[x][i-1]-2
            if len(S_h[y]) == 0:
                c += W-1
            else:
                i = bisect_left(S_h[y],x)
                if i == 0:
                    c += S_h[y][0]-1
                elif i == len(S_h[y]):
                    c += W-S_h[y][-1]-2
                else:
                    c += S_h[y][i]-S_h[y][i-1]-2
            ans = max(ans,c)

print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
S = [input() for i in range(H)]

S_h1 = [[0]*(W+1) for i in range(H)]
S_w1 = [[0]*(H+1) for i in range(W)]
S_h2 = [[0]*(W+1) for i in range(H)]
S_w2 = [[0]*(H+1) for i in range(W)]

for x in range(W):
    for y in range(H):
        if S[y][x] == '#':
            S_h1[y][x] = 0
            S_w1[x][y] = 0
        else:
            S_h1[y][x] += S_h1[y][x-1]+1
            S_w1[x][y] += S_w1[x][y-1]+1

for x in range(W-1,-1,-1):
    for y in range(H-1,-1,-1):
        if S[y][x] == '#':
            S_h2[y][x] = 0
            S_w2[x][y] = 0
        else:
            S_h2[y][x] += S_h2[y][x+1]+1
            S_w2[x][y] += S_w2[x][y+1]+1

ans = 0
for x in range(W):
    for y in range(H):
        if S[y][x] == '.':
            ans = max(ans,S_h1[y][x]+S_h2[y][x]+S_w1[x][y]+S_w2[x][y]-3)
 
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList: Set[Cod] = []
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        args = input().split()
        item = (int(args[0]), int(args[1]))
        codList.append(item)
        columnSumList[item[1] - 1] += 1
        rowSumList[item[0] - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if (row + 1, column + 1) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList = {}
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.setdefault(h, {})
        codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if row + 1 in codList and column + 1 in codList[row + 1]:
                continue
            else:
                print(result)
                return

    print(result - 1)


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

N = int(input())
item_list = []
for n in range(N):
    item = str(input())
    if item_list.count(item) == 0:
        item_list.append(item)

print(len(item_list))


### FIXED CODE ###

N = int(input())
item_list = []
for n in range(N):
    item_list.append(str(input()))

#     item = str(input())
#     if item_list.count(item) == 0:
#         item_list.append(item)
#
# print(len(item_list))

item_set = (set(item_list))
print(len(item_set))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sx,sy,tx,ty=map(int,input().split())
n=int(input())
p=[(sx,sy,0)]
for _ in range(n):
  x,y,r=map(int,input().split())
  p.append((x,y,r))
p.append((tx,ty,0))
n+=2
edge=[[]for _ in range(n)]
for i in range(n-1):
  for j in range(i+1,n):
    sx,sy,sr=p[i]
    tx,ty,tr=p[j]
    t=(abs(sx-tx)**2+abs(sy-ty)**2)**0.5
    c=max(0,t-(sr+tr))
    edge[i].append((j,c))
    edge[j].append((i,c))
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  root=[-1]*n
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        root[u]=v
        heappush(h,[c+t,u])
  return ans
d=dijkstra(0,n,edge)
print(d[n-1])

### FIXED CODE ###

import sys
input=sys.stdin.readline
sx,sy,tx,ty=map(int,input().split())
n=int(input())
p=[(sx,sy,0)]
for _ in range(n):
  x,y,r=map(int,input().split())
  p.append((x,y,r))
p.append((tx,ty,0))
n+=2
edge=[[]for _ in range(n)]
for i in range(n-1):
  for j in range(i+1,n):
    sx,sy,sr=p[i]
    tx,ty,tr=p[j]
    t=(abs(sx-tx)**2+abs(sy-ty)**2)**0.5
    c=max(0,t-(sr+tr))
    edge[i].append((j,c))
    edge[j].append((i,c))
from heapq import heappop,heappush
inf=10**20
ans=[inf]*n
ans[0]=0
root=[-1]*n
h=[(0,0)]
while h:
  c,v=heappop(h)
  if ans[v]<c:continue
  for u,t in edge[v]:
    if c+t<ans[u]:
      ans[u]=c+t
      root[u]=v
      heappush(h,(c+t,u))
print(ans[n-1])
### BUGGY CODE ###

from collections import deque

s = input()
q = int(input())
query = [input().split() for i in range(q)]

d = deque(['S'])

#d = ['S']

rev = 0

for i in range(q):
    if query[i][0] == '2':
        if query[i][1] == '1':
            d.appendleft(query[i][2])
        else:
            d.append(query[i][2])
    else:
        d.reverse()
        rev += 1

#ans = deque()

if rev % 2 == 1:
    #s = ''.join(list(reversed(s)))
    s = s[::-1]

while len(d):
    tmp = d.popleft()
    if tmp == 'S':
        #ans.append(s)
        print(s,end='')
    else:
        print(tmp,end='')
        #ans.append(tmp)

#print(*ans,sep='')


### FIXED CODE ###

from collections import deque

s = input()
q = int(input())
query = [input().split() for i in range(q)]

d = deque(['S'])

#d = ['S']

rev = False

for i in range(q):
    if query[i][0] == '1':
        rev = not rev
        continue
    
    if not rev:
        if query[i][0] == '2':
            if query[i][1] == '1':
                d.appendleft(query[i][2])
            else:
                d.append(query[i][2])
    else:
        if query[i][0] == '2':
            if query[i][1] == '1':
                d.append(query[i][2])
            else:
                d.appendleft(query[i][2])

#ans = deque()
if rev:
    #d = ''.join(list(reversed(d)))
    s = s[::-1]



while len(d):
    if rev:
        tmp = d.pop()
    else:
        tmp = d.popleft()
    if tmp == 'S':
        #ans.append(s)
        print(s,end='')
    else:
        print(tmp,end='')
        #ans.append(tmp)

#print(*ans,sep='')
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
edge = ['#'] * (W + 2)
field = [edge]
q = deque()

for i in range(H):
    line = input()
    field.append(['#'] + list(line) + ['#'])
    for j in range(W):
        if line[j] == '#':
            q.append((i + 1, j + 1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    if field[y + 1][x] == '.':
        field[y + 1][x] = '#'
        q.append((y + 1, x, lv + 1))

    if field[y - 1][x] == '.':
        field[y - 1][x] = '#'
        q.append((y - 1, x, lv + 1))

    if field[y][x+1] == '.':
        field[y][x+1] = '#'
        q.append((y, x+1, lv + 1))

    if field[y][x-1] == '.':
        field[y][x-1] = '#'
        q.append((y, x-1, lv + 1))

print(res)

### FIXED CODE ###

from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    field.append(['#'] + list(input()) + ['#'])
    for j in range(W):
        if field[i+1][j+1] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

print(res)
### BUGGY CODE ###

import sys
import math
import heapq
import collections

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

### FIXED CODE ###

from collections import*
from bisect import*
s=input()
n=len(s)
t=input()
d=defaultdict(list)
for i,c in enumerate(s):
    d[c].append(i)
m=-1
o=0
for c in t:
    if not d[c]:
        print(-1)
        exit()
    i=bisect(d[c],m)
    if len(d[c])==i:
        o+=1
        m=d[c][0]
    else:
        m=d[c][i]
print(o*n+m+1)
### BUGGY CODE ###

class DualSegTree():
    def __init__(self,n):
        self.n=n
        self.data=[0]*n*2
    def propagate(self,i):
        if i>=self.n*2:return
        data=self.data
        c,j=0,i
        while j:
            j>>=1
            c+=1
        for j in range(c-1,0,-1):
            j=i>>j
            data[j+j]+=data[j]
            data[j-~j]+=data[j]
            data[j]=0
    def update(self,l,r,x):
        data=self.data
        l+=self.n
        r+=self.n
        self.propagate(l)
        self.propagate(r)
        while l<r:
            if l&1:
                data[l]+=x
                l+=1
            if r&1:
                r-=1
                data[r]+=x
            l>>=1
            r>>=1
    def get(self,i):
        i+=self.n
        self.propagate(i)
        return self.data[i]
def main():
    n,k,*a=map(int,open(0).read().split())
    seg=DualSegTree(n)
    for i,b in enumerate(a,n):
        seg.data[i]=b
    for _ in range(k):
        d=DualSegTree(n)
        m=10**18
        for i in range(n):
            t=seg.get(i)
            if t<m:m=t
            d.update(max(0,i-t),min(i-~t,n),1)
        seg=d
        if m==n:break
    print(*[seg.get(i)for i in range(n)])
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()
### BUGGY CODE ###

#!/usr/bin/env python

import random

class Dice:
    def __init__(self, top, s, e, w, n, bottom):
        self.top    = top
        self.s      = s
        self.e      = e
        self.w      = w
        self.n      = n
        self.bottom = bottom

    def rotate(self, dist):
        if dist == 'N':
            self.top, self.s, self.n, self.bottom = self.s, self.bottom, self.top, self.n 
        elif dist == 'S':
            self.s, self.bottom, self.top, self.n = self.top, self.s, self.n, self.bottom 
        elif dist == 'E':
            self.top, self.e, self.w, self.bottom = self.w, self.top, self.bottom, self.e 
        elif dist == 'W':
            self.w, self.top, self.bottom, self.e = self.top, self.e, self.w, self.bottom 

if __name__ == '__main__':
    dice1 = Dice(*map(int, raw_input().split()))
    dice2 = Dice(*map(int, raw_input().split()))

    ref1 = dict()
    ref2 = dict()
    while len(ref1)<24:
        ref1[(dice1.top, dice1.s)] = dice1.e
        ref2[(dice2.top, dice2.s)] = dice2.e

        dist = 'NSEW'[random.randint(0,3)]
        dice1.rotate(dist)
        dice2.rotate(dist)

    print 'Yes' if ref1==ref2 else 'No'



### FIXED CODE ###

#!/usr/bin/env python

import random

class Dice:
    def __init__(self, top, s, e, w, n, bottom):
        self.top    = top
        self.s      = s
        self.e      = e
        self.w      = w
        self.n      = n
        self.bottom = bottom

    def rotate(self, dist):
        if dist == 'N':
            self.top, self.s, self.n, self.bottom = self.s, self.bottom, self.top, self.n 
        elif dist == 'S':
            self.s, self.bottom, self.top, self.n = self.top, self.s, self.n, self.bottom 
        elif dist == 'E':
            self.top, self.e, self.w, self.bottom = self.w, self.top, self.bottom, self.e 
        elif dist == 'W':
            self.w, self.top, self.bottom, self.e = self.top, self.e, self.w, self.bottom 

if __name__ == '__main__':
    dice1 = Dice(*map(int, raw_input().split()))
    dice2 = Dice(*map(int, raw_input().split()))

    ref1 = set()
    ref2 = set()
    for _ in range(1000):
        if len(ref1) > 23:
            break

        ref1.add((dice1.top, dice1.s, dice1.e))
        ref2.add((dice2.top, dice2.s, dice2.e))

        dist = 'NSEW'[random.randint(0,3)]
        dice1.rotate(dist)
        dice2.rotate(dist)

    print 'Yes' if ref1==ref2 else 'No'
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))

L.sort(reverse=True)
counter = 0

for index1,c in enumerate(L):
    index2 = index1+1
    if index2>N-1:
      break
    b = L[index2]
    while b>=c/2:
        
        index3 = index2+1
        if index3>N-1:
            break
        a = L[index3]
        
        while a+b>c:
            counter += 1
            index3+=1
            if index3>N-1:
                break
            a = L[index3]

        index2+=1
        if index2>N-1:
            break
        b = L[index2]


print(counter)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))

L.sort(reverse=True)
counter = 0
import bisect

for index1,c in enumerate(L):
    for index2,b in enumerate(L[index1+1:],start=index1+1):
        left = 0 ; right = N
        oppai = c-b
        while left+1<right:
            mid = (left+right)//2
            if L[mid]>oppai:
                left = mid
            else :
                right=mid
        
        index3 = left
        
        if index3>index2:

            counter += index3-index2
print(counter)
### BUGGY CODE ###

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

for i in range(Q):
    l,r = map(int,input().split())
    for j in range(r-l-1):
        if S[j] == 'A':
            if S[j+1] == 'C':
                count += 1
    print(count)
    count = 0

### FIXED CODE ###

N,Q = map(int,input().split())
S = list(input())
AC_list=[]
sum_AC=0
sum_list=[]
Ans=[]

for i in range(N-1):
    if S[i]=='A':
        if S[i+1]=='C':
            AC_list.append(1)
        else:
            AC_list.append(0)
    else:
        AC_list.append(0)

    sum_AC = sum_AC+int(AC_list[i])
    sum_list.append(sum_AC)

for j in range(Q):

    l,r=map(int,input().split())
    if l == 1 :
        Ans.append(sum_list[r-2])
    else:
        Ans.append(sum_list[r-2]-sum_list[l-2])

for k in range(Q):
    print(Ans[k])
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if L[i] + L[j] <= L[k]:
                break
            ans += 1
print(ans)


### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        index = bisect.bisect_left(L, L[i] + L[j])
        ans += max(0, index - j - 1)
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
p_list = list(map(int, input().split()))
score = []
for p in p_list:
    score.append((p + 1) / 2)

max_score = 0
for i in range(n - k + 1):
    max_score = max(max_score, sum(score[i:(i+k)]))
print(max_score)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
p_list = list(map(int, input().split()))
score = []
for p in p_list:
    score.append((p + 1) / 2)

max_score = 0
flag = 0
total_score = 0
for i in range(n):
    if i < k - 1:
        total_score += score[i]
    else:
        total_score += score[i]
        max_score = max(max_score, total_score)
        total_score -= score[i - k + 1]
print(max_score)