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

import sys


def print_err(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


def main():
    """
    0 と 1 からなる文字列 S が与えられます。
    以下の操作を好きな回数繰り返すことで S の要素をすべて 0 にできるような、|S| 以下の最大の整数 K を求めてください。
    S の長さ K 以上の連続する区間 [l,r] を選ぶ(すなわち、r−l+1≥K が満たされる必要がある)。
    l≤i≤r なるすべての整数 i に対し、Si が 0 なら Si を 1 に、Si が 1 なら Si を 0 に置き換える。
    制約
    1≤|S|≤105
    Si(1≤i≤N) は 0 または 1 である
    """
    S = input()

    f(S)


def f(S):
    """
    最大となるKより、1つずつ変えるのは最後の手段
    ※K以上の反転可能であるため

    000: OK
    001, 110:  -> 100, 011
    010, 101:
      11を最終的に反転するように修正していく
        101: 1-3 all
        011: 1-2
        000: 2-3
    011, 100: 11を反転でOK

    0001 となっているとき
    K=3とすれば
    000 をまず反転、その後K+1まで反転すれば、初期状態からK+1番目のみ反転できる
    """
    n = len(S)
    ans = n

    # 反転確認
    table = str.maketrans('01', '10')
    for k in range(1, n):
        if S[k] == S[k - 1]:
            continue

        t = max(k, n - k)
        ans = min(ans, t)

        t = max(k, n - k)
        # 反転を利用して異なる部分を変更
        # 要素数の多い方を対称の異なる文字含めて反転
        if t == k:
            S = S[:t].translate(table) + S[t:]
        else:
            S = S[:k] + S[k:].translate(table)

        print_err("t:", t, "k:", k, "S:", S, sep="\t")

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

change = False
debug = False


def print_err(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


def main():
    """
    0 と 1 からなる文字列 S が与えられます。
    以下の操作を好きな回数繰り返すことで S の要素をすべて 0 にできるような、|S| 以下の最大の整数 K を求めてください。
    S の長さ K 以上の連続する区間 [l,r] を選ぶ(すなわち、r−l+1≥K が満たされる必要がある)。
    l≤i≤r なるすべての整数 i に対し、Si が 0 なら Si を 1 に、Si が 1 なら Si を 0 に置き換える。
    制約
    1≤|S|≤105
    Si(1≤i≤N) は 0 または 1 である
    """
    S = input()

    f(S)


def f(S):
    """
    最大となるKより、1つずつ変えるのは最後の手段
    ※K以上の反転可能であるため

    000: OK
    001, 110:  -> 100, 011
    010, 101:
      11を最終的に反転するように修正していく
        101: 1-3 all
        011: 1-2
        000: 2-3
    011, 100: 11を反転でOK

    0001 となっているとき
    K=3とすれば
    000 をまず反転、その後K+1まで反転すれば、初期状態からK+1番目のみ反転できる
    """
    n = len(S)
    ans = n

    # 反転確認
    table = str.maketrans('01', '10')
    for k in range(1, n):
        if S[k] == S[k - 1]:
            continue

        t = max(k, n - k)
        ans = min(ans, t)

        # 反転を利用して異なる部分を変更
        # 要素数の多い方を対称の異なる文字含めて反転

        # CPython3, PyPy: TLE
        if change:
            if t == k:
                S = S[:t].translate(table) + S[t:]
            else:
                S = S[:k] + S[k:].translate(table)

            if debug:
                print_err("t:", t, "k:", k, "S:", S, sep="\t")

    print(ans)

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

n = int(input())
a_list = list(map(int, input().split()))
count = 0

for i in range(1, n):
    for j in range(i+1, n+1):
        if j - i == a_list[i-1] + a_list[j-1]:
            count += 1
print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
count = 0
d={}
for i in range(n):
    if i - a[i] in d:
        count+=d[i - a[i]]
    if i + a[i] in d:
        d[i+a[i]] += 1
    else:
        d[i+a[i]] = 1

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

def main():
    s = input()
    answer = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            now = int(s[i:j + 1])
            if now < 2019:
                continue
            elif now % 2019 == 0:
                answer += 1
    print(answer)


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    s = input()
    mod = 2019
    mod_count = {i: 0 for i in range(mod)}
    now_num = 0
    base = 1
    for i in range(len(s) - 1, -1, -1):
        mod_count[now_num] += 1
        now_num += base * int(s[i])
        now_num %= mod
        base *= 10
        base %= mod
    ans = 0
    mod_count[now_num % mod] += 1
    for i in range(mod):
        ans += mod_count[i] * (mod_count[i] - 1) // 2
    print(ans)


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

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * pow(i+1, mod - 2, mod) % mod
    return res

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
all_patern = pow(2, n) - 1
minus_a = combination(n, a)
minus_b = combination(n, b)
print((all_patern % mod - minus_a - minus_b) % mod)

### FIXED CODE ###

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * pow(i+1, mod - 2, mod) % mod
    return res

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
all_patern = pow(2, n, mod) - 1
minus_a = combination(n, a)
minus_b = combination(n, b)
print((all_patern - minus_a - minus_b) % mod)
### BUGGY CODE ###

import sys
from collections import defaultdict

n, m = map(int, input().split())

wa=defaultdict(lambda: 0)
ac=set()
cnt = 0
for line in sys.stdin:
  p, s = line.split()
  p = int(p)
  if p in set(ac):
    continue

  if s == "AC":
    cnt+=1
    ac.add(p)
  else:
    wa[p] += 1

print(cnt, sum(wa[i] for i in ac))

### FIXED CODE ###

import sys
from collections import defaultdict

n, m = map(int, input().split())

wa=defaultdict(lambda: 0)
already=set()
ac = 0
for line in sys.stdin:
  p, s = line.split()
  p = int(p)
  if p in already:
    continue

  if s == "AC":
    ac+=1
    already.add(p)
  else:
    wa[p] += 1

print(ac, sum(wa[i] for i in already))
### BUGGY CODE ###

def euc(i, j):
    if i > j:
        i, j = j, i
    while j%i != 0:
        k = abs(j - i)
        if k > i:
            i, k = k, i
        j = i%k
        if j == 0:
            return(k)
        i = k
        if i > j:
            i, j = j, i
    return i


N = int(input())
sum = 0
for i in range(1, N + 1):
    for j in range(1, N + 1): 
        ij = euc(i, j)
        for k in range(1, N + 1):
            sum += euc(ij, k)
print(sum)

#print(euc(2, 3))


### FIXED CODE ###

def euc(i, j):
    if i > j:
        i, j = j, i
    while j%i != 0:
        k = j - i
        if k > i:
            i, k = k, i
        j = i%k
        if j == 0:
            return(k)
        i = k
        if i > j:
            i, j = j, i
    return i


N = int(input())
sum = 0
for i in range(1, N + 1):
    for j in range(1, N + 1): 
        ij = euc(i, j)
        for k in range(1, N + 1):
            sum += euc(ij, k)
print(sum)

#print(euc(2, 3))
### BUGGY CODE ###

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


def bsearch(l, lsum, rsum):
    n = int(len(l)/2)
    if n == 0:
        return [max(rsum, lsum) , min(rsum, lsum) + l[0]]
    ll = l[:n]
    rl = l[n:]
    llsum = sum(ll)
    rrsum = sum(rl)
    lsum += llsum
    rsum += rrsum
    if lsum > rsum:
        return bsearch(ll, lsum-llsum, rsum)
    else:
        return bsearch(rl, lsum, rsum-rrsum)

for i in range(N-3):
    cs = bsearch(As[:i+2], 0, 0) + bsearch(As[i+2:], 0, 0)
    if i == 0:
        result = max(cs) - min(cs)
    else:
        if max(cs) - min(cs) < result:
            result = max(cs) - min(cs)
print(result)


### FIXED CODE ###

import random
from itertools import accumulate
N = int(input())
As = [int(i) for i in input().split(' ')]

#N = pow(10, 4)
#As = [random.randint(0,1000) for r in range(N)] 
As = list(accumulate(As))


def bsearch(L, l, r, ls, rs):
    if r - l == 0:
        l_temp = L[l-1] if l!=0 else 0
        lsum = l_temp - ls
        return [max(lsum, rs - L[l]), min(lsum, rs - L[l]) + L[l] - l_temp]
    n = int((r-l)/2)
    lsum = L[l+n] - ls
    rsum = rs - L[l+n]
    if lsum > rsum:
        return bsearch(L, l, l+n, ls, rs)
    else:
        return bsearch(L, l+n+1, r, ls, rs)

for i in range(N-3):
    cs = bsearch(As, 0, i+1, 0, As[i+1]) + bsearch(As ,i+2, N-1, As[i+1], As[-1])
    if i == 0:
        result = max(cs) - min(cs)
    else:
        if max(cs) - min(cs) < result:
            result = max(cs) - min(cs)
print(result)
### BUGGY CODE ###

def inpl():
    return list(map(int, input().split()))


N, X, Y = inpl()
X -= 1
Y -= 1
ans = {}
for i in range(N):
    for j in range(i + 1, N):
        c = min(j - i, abs(i - X) + 1 + abs(j - Y), abs(i - Y) + 1 + abs(j - X))
        ans[c] = ans.get(c, 0) + 1

for i in range(1, N):
    print(ans.get(i, 0))


### FIXED CODE ###

def inpl():
    return list(map(int, input().split()))


N, X, Y = inpl()
X -= 1
Y -= 1
ans = {i: 0 for i in range(N)}
for i in range(N):
    for j in range(i + 1, N):
        c = min(j - i, abs(i - X) + 1 + abs(j - Y), abs(i - Y) + 1 + abs(j - X))
        ans[c] += 1

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

a = int(input())
b = list(map(int,input().split()))
c = []
for val in range(a):
    c.append(5)
for val in range(a):
    c[b[val]-1] = val+1
d = str()
for val in c:
    d = d + str(val) + " "
d = d.rstrip()
print(d)

### FIXED CODE ###

a = int(input())
b = list(map(int,input().split()))
c = []
for val in range(a):
    c.append(5)
for val in range(a):
    c[b[val]-1] = val+1
d = str()
for val in range(len(c)-1):
    print(c[val], end = ' ')
print(c[-1])
### BUGGY CODE ###

N, Q = map(int, input().split())
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

#print(N, Q)
#print(STX)
#print(D)

for d in D:
  mindist = 10 ** 9
  for x in STX:
    if x[0] < x[2] + d + 0.5 < x[1]:
      if x[2] < mindist:
        mindist = x[2]
  if mindist == 10 ** 9:
    print(-1)
  else:
    print(mindist)

### FIXED CODE ###

# E - Roadwork
# https://atcoder.jp/contests/abc128/tasks/abc128_e

from heapq import heappop, heappush
from collections import defaultdict

n, q = map(int,input().split())
task = []
for _ in range(n): 
  s, t, x = map(int, input().split())
  task.append((t - x, 0, x)) 
  task.append((s - x, 1, x)) 

for i in range(q):
  d = int(input())
  task.append((d, 2, i)) 

answer = [-1] * q

task.sort()

se = set()
se_hp = []

for a, b, c in task:
  if b == 0:
    se.remove(c)
  elif b == 1:
    se.add(c)
    heappush(se_hp, c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str, answer)))
### BUGGY CODE ###

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

dp=[0 for _ in range(N+1)]

for i in range(0,N):
    x=h[i]
    dp[x]=max(dp[:x+1])+a[i]

print(max(dp))


### FIXED CODE ###

class SegTree():
    # init_valは配列の初期値、self.numはn以上の最小のべき乗 O(N)
    def __init__(self,init_val,segfunc,ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n-1).bit_length()
        # self.treeは0～2n-2の配列を使う
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i - 1] = init_val[i]

        for i in range(self.num-2,-1,-1):
            self.tree[i]=self.segfunc(self.tree[2*i+1],self.tree[2*i+2])

    # k番目をxに更新 O(logN)
    def update(self,k,x):
        k += self.num - 1
        self.tree[k]=x
        while k:
            k=(k-1)//2
            self.tree[k]=self.segfunc(self.tree[2*k+1],self.tree[2*k+2])

    # 区間[l,r)でsegfuncした結果を返す O(logN)
    def query(self,l,r):
        res = self.ide_ele

        l += self.num-1
        r += self.num-2
        while r>=l:
            if l & 1 == 0:
                res = self.segfunc(res,self.tree[l])
            if r & 1 == 1:
                res = self.segfunc(res,self.tree[r])
                r -= 1
            l = l // 2
            r = (r-1) // 2
        return res

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


dp=[0 for _ in range(N+1)]

def segfunc(x,y):
    return max(x,y)

ide_ele=-100

seg=SegTree(dp,segfunc,ide_ele)

for i in range(0,N):
    x=h[i]
    A=seg.query(0,x+1)
    seg.update(x,A+a[i])


print(seg.query(0,N+1))
### BUGGY CODE ###

def main():
  from sys import exit
  n = int(input())
  a = [list(map(int, input().split())) for _ in range(n)]
  ilist = [0] * n
  days = 1
  while True:
    booked = set()
    books = 0
    for i in range(n):
      ii = ilist[i]
      if ii == n - 1:
        continue
      j = a[i][ii] - 1
      if a[j][ilist[j]] - 1 != i:
        continue
      if (i in booked) or (j in booked):
        continue
      books += 1
      booked.add(i)
      booked.add(j)
      ilist[i] += 1
      ilist[j] += 1
    if books == 0:
      print(-1)
      exit()
    if all(i == n - 1 for i in ilist):
      break
    days += 1
  print(days)
main()


### FIXED CODE ###

from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id_db = [[0] * N for _ in range(N)]

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id_db[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id_db)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()
### BUGGY CODE ###

from collections import deque
def main():
  h,w=map(int,input().split())
  ans,q=0,deque()
  visited=[[0 if j=="#" else -1 for j in input()] for _ in range(h)]
  q=deque([(i,j) for i in range(h) for j in range(w) if visited[i][j]==0])
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if visited[newx][newy]==-1:
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()


### FIXED CODE ###

from collections import deque
def main():
  h,w=map(int,input().split())
  hw=h*w
  maze=[list(input()) for i in range(h)]
  visited=[[hw]*w for i in range(h)]
  ans,q=0,deque()
  for i in range(h):
    for j in range(w):
      if maze[i][j]=='#':
        q.append((i,j))
        visited[i][j]=0
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='#' and visited[newx][newy]==hw:
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

# coding: utf-8
class SqrtDecomposition:
    # RMQ用平方分割
    
    # n:要素数 init:配列初期値
    def __init__(self,n,init=0):
        self.data=[init for i in range(n)]
        self.sqrt_n=int(n**0.5)+1
        self.bucket=[init for i in range(self.sqrt_n)]
    
    # x を y にする
    def update(self,x,y):
        self.data[x] = y
        tmp = self.data[x//self.sqrt_n * self.sqrt_n]
        for i in range(x//self.sqrt_n * self.sqrt_n, min(x//self.sqrt_n * self.sqrt_n + self.sqrt_n, n)):
            if tmp > self.data[i]:
                tmp = self.data[i]
        self.bucket[x//self.sqrt_n] = tmp
    
    # [x,y) の最小を求める
    def find(self,x,y):
        tmp = 10**19
        for i in range(self.sqrt_n):
            l,r=i*self.sqrt_n,(i+1)*self.sqrt_n
            if r <= x or y <= l :
                continue
            if x <= l and r <= y :
                tmp = min(tmp, self.bucket[i]);
            else:
                for j in range(max(x, l),min(y, r)):
                    tmp = min(tmp, self.data[j]);
        return tmp


n,q = map(int,input().split())
sd=SqrtDecomposition(n,2**31-1)
for i in range(q):
    c,x,y=map(int,input().split())
    if c==0:
        sd.update(x,y)
    else:
        print(sd.find(x,y+1))





### FIXED CODE ###

# coding: utf-8
class seg_tree:
    def __init__(self,n,minimum=True):
        self.inf = 2**31-1
        self.size = 2**(len(bin(n-1))-2)*2-1
        self.minimum = minimum
        if self.minimum:
            self.tree = [self.inf for i in range(self.size)]
        else:
            self.tree = [-1 for i in range(self.size)]
     
    def data(self):
        return self.tree[self.size//2:]
 
    def update(self,i,x):
        i=self.size//2+i
        self.tree[i]=x
        if self.minimum:
            while 1:
                i=(i-1)//2
                self.tree[i]=min(self.tree[i*2+1],self.tree[i*2+2])
                if i<=0:
                    break
        else:
            while 1:
                i=(i-1)//2
                self.tree[i]=max(self.tree[i*2+1],self.tree[i*2+2])
                if i<=0:
                    break
 
    def _mincheck(self,s,t,l,r,_p=0):
        if s<=l and r<=t:
            return self.tree[_p]
        elif r<s or t<l:
            return self.inf
        else:
            return min(self._mincheck(s,t,l,l+(r-l)//2,_p*2+1),self._mincheck(s,t,l+(r-l)//2+1,r,_p*2+2))
     
    def _maxcheck(self,s,t,l,r,_p=0):
        if s<=l and r<=t:
            return self.tree[_p]
        elif r<s or t<l:
            return -1
        else:
            return max(self._maxcheck(s,t,l,l+(r-l)//2,_p*2+1),self._maxcheck(s,t,l+(r-l)//2+1,r,_p*2+2))
 
    def find(self,s,t):
        if self.minimum:
            return self._mincheck(s,t,0,self.size//2)
        else:
            return self._maxcheck(s,t,0,self.size//2)
 
n,q=map(int,input().split())
st=seg_tree(n)
ans=[]
for i in range(q):
    c,x,y=map(int,input().split())
    if c:
        ans.append(st.find(x,y))
    else:
        st.update(x,y)
print(*ans,sep='\n')
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
S = list(input())

if S[0]!='B' or S[-1]!='B':
    print(0)
    exit()

mod = 10**9 + 7
cnt_l = 1
cnt_r = 0
pre_s = 'B'
pre_d = 1 #1がleft
ans = 1

for i,s in enumerate(S[1:]):
    if pre_s==s:
        if pre_d:
            pre_d = 0
            ans *= cnt_l - cnt_r #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
            cnt_r += 1
        else:
            pre_d = 1
            cnt_l += 1
    else:
        if pre_d:
            cnt_l += 1
        else:
            ans *= cnt_l - cnt_r #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
            cnt_r += 1
    pre_s = s

for i in range(1,N+1):
    ans *= i
    ans %= mod
if cnt_l!=N:
    print(0)
    exit()

print(ans)

### FIXED CODE ###

import math
n = int(input())
S = input()
 
RL = [None]*2*n
 
for i in range(2*n):
    if i % 2 == 0:
        if S[i] == 'B':
            RL[i] = 'L'
        else:
            RL[i] = 'R'
 
    else:
        if S[i] == 'B':
            RL[i] = 'R'
        else:
            RL[i] = 'L'
 
if S[0] == 'W' or S[-1] == 'W':
    print(0)
    exit()
 
left = 0
count = 1
mod = 10**9 + 7
 
for check in RL:
    if check == 'L':
        left += 1
    else:
        count = count * left % mod
        left -= 1
 
    if left < 0:
        print(0)
        exit()
 
count = count * math.factorial(n) % mod
 
if left != 0:
    print(0)
else:
    print(count)
### BUGGY CODE ###

n,m=map(int, input().split())
s=[input().split() for i in range(m)]

def qa(s):
    qa_dict = {}
    target_q = []
    WAs=0
    ACs=0
    for t in s:
        if t[1] == 'AC':
            target_q.append(t[0])
    target_q = sorted(list(set(target_q)))
    for q in target_q:
        qa_dict[q] = []
        for a in s:
            if a[0] == q:
                qa_dict[q].append(a[1])
                if a[1] == 'AC':
                    break
                else:
                    continue
    for v in qa_dict.values():
        WAs += (len(v) - 1)
        ACs += 1
    return ACs, WAs

if m == 0:
    ac, wa = 0, 0
else:
    ac, wa = qa(s)
print('{} {}'.format(ac, wa))


### FIXED CODE ###

n,m=map(int, input().split())
s=[input().split() for i in range(m)]

def qa(s):
    qa_dict = {}
    WAs=0
    ACs=0
    for qa in s:
        qa_dict[qa[0]] = 0
    for qa in s:
        if qa_dict[qa[0]] <= 0:
            if qa[1] == 'WA':
                qa_dict[qa[0]] -= 1
            elif qa[1] == 'AC':
                if qa_dict[qa[0]] == 0:
                    qa_dict[qa[0]] += 0.001
                else:
                    qa_dict[qa[0]] *= -1
                ACs += 1
    for v in qa_dict.values():
        if v > 0:
            WAs += int(v)
    return ACs, WAs

if m == 0:
    ac, wa = 0, 0
else:
    ac, wa = qa(s)
print('{} {}'.format(ac, wa))
### BUGGY CODE ###

N=int(input())
S=input()
#print(S[1])
cnt=0
for k in range(1,N+1):
  for j in range(1,k):
    for i in range(1,j):
      if (j-i)!=(k-j):
        if S[i-1]!=S[j-1] and S[i-1]!=S[k-1] and S[j-1]!=S[k-1]:
          cnt += 1
          #print(i,j,k,j-i,k-j, S[i-1],S[j-1],S[k-1])
print(cnt)

### FIXED CODE ###

N=int(input())
S=input()

r=S.count('R')
g=S.count('G')
b=S.count('B')
al_num=r*g*b

#全体からj-i=k-jの場合を引く
sub=0
for i in range(0,N):
  for j in range(i+1,N):
    if S[i]==S[j]:
      continue

    k = 2*j -i
    #i,j,kは等差数列なのでkは決まる, k>=Nは不適なのでスキップ
    if k>=N or S[k]==S[i] or S[k]==S[j]:
      continue
    
    sub += 1
print(al_num - sub)
# O(N^2)
### BUGGY CODE ###

n=int(input())

s=0
for i in range(n):
    s += i
    
print(s)

### FIXED CODE ###

n=int(input())

s=int(n*(n-1)//2)
    
print(s)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

import copy
ans = 0

for i in range(N-1):
    B = copy.copy(A)
    del B[:i+1]
    for j in range(len(B)):
        ans += A[i] * B[j] % MOD
        ans = ans % MOD
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

import copy
B = copy.copy(A)
C = sum(B)
ans = 0

for i in range(N-1):
    C = (C - B[i]) % MOD
    ans += A[i] * C % MOD
    ans = ans % MOD
print(ans)
### BUGGY CODE ###

n = int(input())
arr = list(map(int, input().split()))
k = int(input())
for _ in range(k):
  a,b = map(int, input().split())
  for i in range(len(arr)):
    if arr[i] == a:
      arr[i] = b
  print(sum(arr))

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
k = int(input())
s = sum(arr)
d = {}
for i in arr:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
for _ in range(k):
    v = 0
    a,b = map(int, input().split())
    if a not in d:
        print(s)
        continue
    s += (b-a) * d[a]
    if b in d:
        d[b] += d[a]
    else:
        d[b] = d[a]
    print(s)
    del d[a]
### BUGGY CODE ###

N = int(input())
X = int(input(), 2)
me = {}
def popcount(n):
    if n in me:
        return me[n]
    me[n] = bin(n).count('1')
    return bin(n).count('1')
memo = {1:1}
def f_count(n):
    co_n = n
    ans = 0
    while n != 0:
        if n in memo:
            ans += memo[n]
            memo[co_n] = ans
            return ans
        n %= popcount(n)
        ans += 1
    memo[co_n] = ans
    return ans

for i in range(N):
    x = X
    if X >> (N-1 -i) & 1:
        x -= 2**(N-1 -i)
    else:
        x += 2**(N-1 -i)
    print(f_count(x))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
N = int(input())
X = input()
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
one_mod, zero_mod = 0, 0

for b in X:
    if one_pop != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop

pop = {0:0}
def popcount(n):
    if n in pop:
        return pop[n]
    pop[n] = popcount(n // 2) + n % 2
    return pop[n]
memo = {0:0}
def f_count(n):
    if n in memo:
        return memo[n]
    memo[n] = f_count(n % popcount(n)) + 1
    return memo[n]
one_p = {0:1}
def one_pow(n):
    if n in one_p:
        return one_p[n]
    one_p[n] = one_pow(n - 1) * 2 % one_pop
    return one_p[n]
zero_p = {0:1}
def zero_pow(n):
    if n in zero_p:
        return zero_p[n]
    zero_p[n] = zero_pow(n - 1) * 2 % zero_pop
    return zero_p[n]
for i in range(N):
    if X[i] == '1' and one_pop == 0:
        print(0)
        continue
    if X[i] == '1':
        x = one_mod
        x -= one_pow(N-1-i)
        x %= one_pop
    elif X[i] == '0':
        x = zero_mod
        x += zero_pow(N-1-i)
        x %= zero_pop
    
    print(f_count(x) + 1)