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

n = int(input())
s = input()
ans = s.count("R")*s.count("G")*s.count("B")

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

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count("R")*s.count("G")*s.count("B")

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

N = int(input())
array = list(map(int, input().split()))
cnt = 0

for i in range(0, N):
    array2 = list(array[0:i+1])
    array2.sort()
    if array2[0] == array[i]:
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
array = list(map(int, input().split()))
cnt = 1
minv = array[0]

for i in range(1, N):
    if minv > array[i]:
        minv = array[i]
        cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input())

A = input().split()
flag = 0

for i in range(N):
    for j in range(i+1,N):
        if A[i]==A[j]:
            flag =1
            break
    if flag == 1:
        break

if flag == 1:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

N = int(input())

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

di={}


for i in range(N):
    di[A[i]] = i 

if len(di)<len(A):
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

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

counter_remove = 0
counter = dict()
counter_keys = []
for i in range(n):
    if a[i] not in counter_keys:
        counter_keys.append(a[i])
        counter[str(a[i])] = 1
    else:
        if counter[str(a[i])] < a[i]:
            counter[str(a[i])] += 1
        else:
            counter_remove += 1

# remove small
for key in counter_keys:
    if counter[str(key)] < int(key):
        counter_remove += int(counter[str(key)])

print(counter_remove)


### FIXED CODE ###

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

from collections import Counter

b = Counter(a)

counter = 0
for key in b.keys():
    if b[key] < key:
        counter += b[key]
    elif b[key] > key:
        counter += b[key] - key
print(counter)
### BUGGY CODE ###

import sys

s = str(sys.stdin.readline())
o = len(s)
for i in range(1000000000000):
    p1 = s.find("01")
    p2 = s.find("10")
    if p1 == -1 and p2 == -1:
        break
    elif p1 == -1:
        i = p2
    elif p2 == -1:
        i = p1
    else:
        i = p1 if p1 < p2 else p2

    s = s[:i] + s[i + 2:]
    
print(o - len(s))

### FIXED CODE ###

import sys

s = str(sys.stdin.readline())
c0 = s.count('0')
c1 = s.count('1')
r = c0 if c0 < c1 else c1
print(r*2)
### 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)))
"""
while len(d):
    tmp = d.popleft()
    if tmp == 'S':
        ans.append(s)
    else:
        ans.append(tmp)
"""
d = [s if i == 'S' else i for i in d]

print(*d,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 ###

N,M=map(int,input().split())
AB=list(list(map(int,input().split())) for _ in range(N))
AB.sort(key=lambda x:x[0])
cost=0
for ab in AB:
    for i in range(ab[1]):
        if M>0:
            M-=1
            cost+=ab[0]
print(cost)

### FIXED CODE ###

N,M=map(int,input().split())
AB=list(list(map(int,input().split())) for _ in range(N))
AB.sort(key=lambda x:x[0])
cost=0
for ab in AB:
    if M>=ab[1]:
        M-=ab[1]
        cost+=ab[0]*ab[1]
    else:
        cost+=ab[0]*M
        break
print(cost)
### BUGGY CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
    if s/k==3 :
        cnt=1
        break
    for y in range(k+1):
        z=s-x-y
        if 0<=z and z<=k:
            sum=x+y+z   
            if sum == s:
                cnt+=1
print(cnt)

### FIXED CODE ###

k,s=map(int,input().split())
cnt=0
for x in range(k+1):
    for y in range(k+1):
        z=s-x-y
        if 0<=z and z<=k:
          cnt+=1
print(cnt)
### BUGGY CODE ###

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

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

ans = []

ways = []

for i in range(m):
    a, b = map(int, input().split())
    if [a, b] not in ways or [b, a] not in ways:
        ways.append([a, b])
        if h[a-1] < h[b-1]:
            if a not in ans:
                ans.append(a)
        elif h[a-1] > h[b-1]:
            if b not in ans:
                ans.append(b)
        elif h[a-1] == h[b-1]:
            if a not in ans:
                ans.append(a)
                if b not in ans:
                    ans.append(b)
            elif b not in ans:
                ans.append(b)

print(n-len(ans))


### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
LIST = [ 1 for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    if H[A-1] >= H[B-1]: LIST[B-1] = 0
    if H[A-1] <= H[B-1]: LIST[A-1] = 0
print(sum(LIST))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
pluslist=[]
minuslist=[]
res=0
for i in range(0,n):
  pluslist.append(a[i]+i)
  minuslist.append(i-a[i])
for i in range(0,n):
  res+=minuslist.count(pluslist[i])
print(res)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
minus={}
plus={}
res=0
for i in range(0,n):
  pp=a[i]
  if i-pp in minus:
    minus[i-pp]+=1
  else:
    minus[i-pp]=1
  if i+pp in plus:
    plus[i+pp]+=1
  else:
    plus[i+pp]=1
for j in range(len(minus)):
  t=minus.popitem()
  try:
    res+=t[1]*plus[t[0]]
  except KeyError:
    pass
print(res)
### BUGGY CODE ###

import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)
N = int(input())
A = list(map(int, input().split()))
RedWine = prod(A)
if RedWine > 1000000000000000000:
    print(-1)
else:
    print(RedWine)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
RedWine = 1
for i in range(N):
    RedWine *= A[i]
    if RedWine > 1000000000000000000:
        break
if RedWine > 1000000000000000000:
    if A.count(0) == 0:
        print(-1)
    else:
        print(0)
else:
    print(RedWine)
### BUGGY CODE ###

import sys
import numpy as np
from numba import njit
 
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def update(A):
  N = len(A)
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    l = max(0, i-x)
    r = min(N-1, i+x)
    B[l] += 1
    if r + 1 < N:
      B[r+1] -= 1
  B = np.cumsum(B)
  return B
    
    
N,K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 50)
for _ in range(K):
  A = update(A)
print(' '.join(A.astype(str)))

### FIXED CODE ###

import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B
 
N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

def main():
    n = int(input())
    v = list(map(int,input().split()))
    o=[]
    e=[]
    checked=[]
    for i in v:
        if not i in checked:
            checked.append(i)
            c0=c1=0
            for j in range(n//2):
                if v[2*j]==i:
                    c0+=1
                if v[2*j+1]==i:
                    c1+=1
            if n%2==1:
                if v[n-1]==i:
                    c1+=1
            o.append([c0,i])
            e.append([c1,i])
    o.append([0,10**6])
    e.append([0,10**6])
    o.sort(reverse=True)
    e.sort(reverse=True)
    if o[0][1]!=e[0][1]:
        print(n-o[0][0]-e[0][0])
        return
    else:
        print(min(n-o[1][0]-e[0][0],n-o[0][0]-e[1][0]))
        return
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    v = list(map(int,input().split()))
    odd={}
    even={}
    for i in range(n):
        if i%2==0:
            if v[i] not in odd:
                odd[v[i]]=1
            else:
                odd[v[i]]+=1
        else:
            if v[i] not in even:
                even[v[i]]=1
            else:
                even[v[i]]+=1
    cnt_o=[]
    cnt_e=[]
    for i in odd:
        cnt_o.append([odd[i],i])
    for i in even:
        cnt_e.append([even[i],i])
    cnt_o.append([0,10**6])
    cnt_e.append([0,10**6])
    cnt_o.sort(reverse=True)
    cnt_e.sort(reverse=True)
    if cnt_o[0][1]!=cnt_e[0][1]:
        print(n-cnt_o[0][0]-cnt_e[0][0])
        return
    else:
        print(min(n-cnt_o[1][0]-cnt_e[0][0],n-cnt_o[0][0]-cnt_e[1][0]))
        return
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
L = []
M = []
for i in range(len(A)):
  if (A[i] not in L):
    L.append(A[i])
for j in range(len(L)):
  M.append(A.count(L[j]))
M.sort()
if (len(M) <= K):
  print(0)
else:
  print(sum(M[:len(M)-K]))

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
A.insert(len(A),0)
L = []
k = 1
for i in range(len(A)-1):
  if (A[i] == A[i+1]):
    k += 1
    i += 1
  else:
    L.append(k)
    k = 1
    i += 1  
L.sort()
if (len(L) <= K):
  print(0)
else:
  print(sum(L[:len(L)-K]))
### BUGGY CODE ###

S = input()
#print(S)
dp = [[0 for _ in range(13)] for _ in range(len(S))]
temp = 0

while dp[len(S) - 1][5] == 0:
  #print(dp)
  if temp == len(S):
    break
  for i in range(13):
    if temp == 0:
      #print(temp, i, S[temp])
      if S[temp] == "?":
        if i <= 9:
          dp[temp][i] = 1
      elif int(S[temp]) == i:
        dp[temp][i] = 1
      continue
    if S[temp] == "?":
      for j in range(13):
        if not i in {(j * 10 + k) % 13 for k in range(10)}:
          continue
        #print(temp, i, j, S[temp])
        dp[temp][i] += dp[temp - 1][j]
    else:
      j = 0
      for k in range(13):
        if (k * 10 + int(S[temp])) % 13 == i:
          j = k
          break
      dp[temp][i] += dp[temp - 1][j]
    dp[temp][i] %= 10 ** 9 + 7
  temp += 1
#print(dp)
print(dp[len(S) - 1][5])

### FIXED CODE ###

S = input()
#S = "19?04??????451??" * (10 ** 5 // 5)
mod = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(len(S))]
if S[0] == "?":
  for i in range(10):
    dp[0][i] = 1
else:
  dp[0][int(S[0])] = 1
#print(dp)
for i in range(len(S) - 1):
  if S[i + 1] == "?":
    for j in range(13):
      for k in range(10):
        dp[i + 1][(j * 10 + k) % 13] += dp[i][j] % mod
  else:
    for j in range(13):
      dp[i + 1][(j * 10 + int(S[i + 1])) % 13] += dp[i][j] % mod
#print(dp)
print(dp[len(S) - 1][5] % (10 ** 9 + 7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():

  s=input()
  s=s.strip("\n")
  n=len(s)
  res=0
  d={key:0 for key in range(2019)}
  t=[0]*(n+1)
  d[0]=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+(int(s[n-i])*10**(i-1))%2019)%2019
      d[t[n-i]]+=1
  for i in d.values():
      if i<2:
        continue
      res+=int(i*(i-1)/2)
  print(res)

if __name__ == '__main__':
  main()

### FIXED CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
      k=k%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

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


import numpy as np

N,K = list(map(int, input().split()))
LRs = [list(map(int, input().split())) for _ in range(K)]

move_list = []
checker = np.zeros(N+1 ,dtype = int)
for LR in LRs:
    for i in range(LR[0], LR[1]+1):
        checker[i] = 1

for index, check in enumerate(checker):
    if(check == 1):
        move_list.append(index)

#print(move_list)

dp = np.zeros(N+1, dtype = int)
dp[1] = 1

for i in range(1, N+1):
    for j in move_list:
        if(i < j):
            break
#        print(i,j)
        dp[i] = (dp[i] +dp[i-j]) % 998244353

print(dp[N])

### FIXED CODE ###

import numpy as np

N,K = list(map(int, input().split()))
LRs = [list(map(int, input().split())) for _ in range(K)]

dp = np.zeros(N+2, dtype = int)
dp[1] = 1
dp[2] = -1

atai = 0
for i in range(1, N+2):
    atai += dp[i]
    for LR in LRs:
        if(i+LR[0] <= N):
            dp[i+LR[0]] = (dp[i+LR[0]] + atai) % 998244353
        if(i+LR[1] <= N):
            dp[i+LR[1]+1] = (dp[i+LR[1]+1] -atai) % 998244353

#    print(dp)

#復元
ruisekiwa = [0]

for hoge in dp:
    ruisekiwa.append(ruisekiwa[-1]+hoge)
print(ruisekiwa[N+1] % 998244353)
### BUGGY CODE ###

import sys
n = int(input())
a = map(int, input().split())

r = 1
for num in a:
  r *= num

if r > 1e18:
  print(-1)
else:
  print(r)


### FIXED CODE ###

import sys
n = int(input())
a = [int(num) for num in input().split()]

if 0 in a:
  print(0)
  sys.exit()

r = 1
for num in a:
  r *= num
  if r > 1e18:
    print(-1)
    sys.exit()

print(r)
### BUGGY CODE ###

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

c = 0
for i in range(N):
    flag = 1
    for j in range(i):
        if P[j] < P[i]: 
            flag = 0 
            break
    if flag:
        c += 1

print(c)

### FIXED CODE ###

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

c = 0
for i in range(N - 1):
    f = P[i]
    l = P[i + 1]
    if f < l:
        P[i] = l
        P[i+1] = f
        c += 1

print(N - c)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
N, Z, W = [int(x) for x in input().strip().split()]
a = [int(x) for x in input().strip().split()]
d = {}
def minmax(x, y, c, f):
    # print('x={}, y={}, c={}, f={}'.format(x, y, c, f))
    if (c, f) in d:
        return d[(c, f)]
    if c == N:
        return abs(x - y)
    if f == 0:
        ret = -float('inf')
        for i in range(1, N - c + 1):
            ret = max(ret, minmax(a[c+i-1], y, c+i, f^1))
    else:
        ret = float('inf')
        for i in range(1, N - c + 1):
            ret = min(ret, minmax(x, a[c+i-1], c+i, f^1))
    d[(c, f)] = ret
    return ret

print(minmax(Z, W, 0, 0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
N, Z, W = [int(x) for x in input().strip().split()]
a = [int(x) for x in input().strip().split()]
d = {}
def minmax(x, y, c, f):
    # print('x={}, y={}, c={}, f={}'.format(x, y, c, f))
    if (c, f) in d:
        return d[(c, f)]
    if c == N:
        return abs(x - y)
    if f == 0:
        ret = -float('inf')
        for i in range(1, N - c + 1):
            ret = max(ret, minmax(a[c+i-1], y, c+i, f^1))
    else:
        ret = float('inf')
        for i in range(1, N - c + 1):
            ret = min(ret, minmax(x, a[c+i-1], c+i, f^1))
    d[(c, f)] = ret
    return ret

print(minmax(Z, W, 0, 0))
### BUGGY CODE ###

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

parent = [None]*N
depth = [0]*N
d = 0
queue = [0]
while queue:
    d += 1
    queue_new = []
    for q in queue:
        for e in E[q]:
            if e==parent[q]: continue
            parent[e] = q
            depth[e] = d
            queue_new.append(e)
    queue = queue_new

ancestor = [[None]*N for _ in range(N)]
for a in range(N):
    for b in range(a, N):
        _a = a
        _b = b
        while _a!=_b:
            if depth[_a] < depth[_b]: _b = parent[_b]
            else: _a = parent[_a]
        ancestor[a][b] = ancestor[b][a] = _a

M = int(input())
P = []
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    w = ancestor[u][v]
    path = set()
    while u!=w:
        _u = parent[u]
        path.add((u, _u))
        u = _u
    while v!=w:
        _v = parent[v]
        path.add((v, _v))
        v = _v
    P.append(path)


ans = 0
n1 = N-1
for k in range(2**M):
    path = set()
    n = 0
    for i, p in enumerate(P):
        if (k>>i)&1:
            path |= p
            n += 1

    if n==0: continue
    sign = +1 if n&1 else -1
    ans += sign * pow(2, n1-len(path))
    
print(pow(2, N-1) - ans)

### FIXED CODE ###

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

parent = [None]*N
depth = [0]*N
d = 0
queue = [0]
while queue:
    d += 1
    queue_new = []
    for q in queue:
        for e in E[q]:
            if e==parent[q]: continue
            parent[e] = q
            depth[e] = d
            queue_new.append(e)
    queue = queue_new

ancestor = [[None]*N for _ in range(N)]
for a in range(N):
    for b in range(a, N):
        _a = a
        _b = b
        while _a!=_b:
            if depth[_a] < depth[_b]: _b = parent[_b]
            else: _a = parent[_a]
        ancestor[a][b] = ancestor[b][a] = _a

M = int(input())
P = []
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    w = ancestor[u][v]
    path = set()
    while u!=w:
        _u = parent[u]
        #path.add((u, _u))
        path.add(u*N+_u)
        u = _u
    while v!=w:
        _v = parent[v]
        #path.add((v, _v))
        path.add(v*N+_v)
        v = _v
    P.append(path)


ans = 0
n1 = N-1
for k in range(2**M):
    path = set()
    n = 0
    for i, p in enumerate(P):
        if (k>>i)&1:
            path |= p
            n += 1

    if n==0: continue
    sign = +1 if n&1 else -1
    ans += sign * pow(2, n1-len(path))
    
print(pow(2, N-1) - ans)
### BUGGY CODE ###

N = int(input())
ret = 0
a = ['3','5','7']
for i in range(357, N+1, 2):
    t = list(set(str(i)))
    t.sort()
    if t == a:
        ret += 1
print(ret)

### FIXED CODE ###

N = int(input())
cnt = 0
def dfs(n, cnt):
    if int(n) > N:
        return cnt
    if n.count("3") >= 1 and n.count("5") >= 1 and n.count("7") >= 1:
        cnt += 1

    for i in ("3","5","7"):
        cnt = max(cnt, dfs(n+i, cnt))
    return cnt

print(dfs("0", 0))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
tu=0
td=0
if k>=50:
  a=[n]*n
else:
  for j in range(k):
    temp=[0]*n
    for i in range(n):
      td=max(i+1-a[i],1)
      temp[td-1]=temp[td-1]+1
      tu=min(i+1+a[i],n)
      if tu!=n:
        temp[tu]=temp[tu]-1
    a[0]=temp[0]
    for i in range(1,n):
      a[i]=a[i-1]+temp[i]
L=[str(t) for t in a]
L=" ".join(L)
print(L)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
tu=0
td=0
if k>=40:
  a=[n]*n
else:
  for j in range(k):
    temp=[0]*n
    for i in range(n):
      td=max(i+1-a[i],1)
      temp[td-1]=temp[td-1]+1
      tu=min(i+1+a[i],n)
      if tu!=n:
        temp[tu]=temp[tu]-1
    a[0]=temp[0]
    for i in range(1,n):
      a[i]=a[i-1]+temp[i]
L=[str(t) for t in a]
L=" ".join(L)
print(L)
### BUGGY CODE ###

import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)
    
    if cnt > ans: continue
    if np.any(kouryo>k): continue

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        wa = wa + kouryo[:, j]
        if np.any(wa>k):
            cnt += 1
            if cnt > ans: break
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)

### FIXED CODE ###

import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

    if cnt > ans: continue
    if np.any(kouryo>k): continue

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        wa += kouryo[:, j]
        if np.max(wa)>k:
            cnt += 1
            if cnt > ans: break
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
S = input()
L = []
R = []
for i in range(q):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)
for i in range(q):    
    print(S[L[i]-1:R[i]].count('AC'))

### FIXED CODE ###

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


import heapq
N = int(input())
nums = list(map(int,input().split(" ")))
nums.sort()
ans = 0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if nums[k] < nums[i] +nums[j]:
                ans +=1
            else:
                break

print(ans)

### FIXED CODE ###

import collections
import heapq
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
nums = list(map(int,input().split(" ")))
nums.sort()
ans = 0
di = collections.defaultdict(lambda :0)
for i in range(N):
    for j in range(i+1,N):
        key = nums[i] + nums[j]
        di[key] += 1
co = 0
for k,v in di.items():
    for temp in nums:
        if k <= temp:
            co += v

temp = combinations_count(N,3)
print(temp- co)