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

def rolling_hash(s):
    l = len(s)
    h = [0]*(l + 1)
    v = 0
    for i in range(l):
        h[i+1] = v = (v * base + ord(s[i])) % mod
    return h
# RH前に、必要な長さの最大値分のpow-tableを計算しておく
def setup_pw(l):
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod
    return pw
def get(h, b, l, r):
    return (h[r] - h[l] * b[r-l]) % mod

N = int(input())
S = input()
mod = 1000000007
base = 37
h1 = rolling_hash(S)
b1 = setup_pw(N)
base = 401
h2 = rolling_hash(S)
b2 = setup_pw(N)
Max = N // 2
broke = False
for i in range(Max-1):
    for j in range(N-2*(Max-i)+1):
        for k in range(N-2*(Max-i)-j+1):
            if get(h1,b1,j,(Max-i)+j) == get(h1,b1,j+(Max-i)+k,2*(Max-i)+j+k) and get(h2,b2,j,(Max-i)+j) == get(h2,b2,j+(Max-i)+k,2*(Max-i)+j+k):
                print(Max-i)
                broke = True
                break
        if broke == True:
            break
    if broke == True:
        break
if broke == False:
    print('0')

### FIXED CODE ###

def rolling_hash(s):
    l = len(s)
    h = [0]*(l + 1)
    v = 0
    for i in range(l):
        h[i+1] = v = (v * base + ord(s[i])) % mod
    return h
def setup_pw(l):
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod
    return pw
def get(h, b, l, r):
    return (h[r] - h[l] * b[r-l]) % mod

def check_bisect(l,h1,b1,h2,b2):
    for j in range(N-2*l+1):
        a1 = get(h1,b1,j,l+j)
        a2 = get(h2,b2,j,l+j)
        for k in range(N-2*l-j+1):
            if a1 == get(h1,b1,j+l+k,2*l+j+k) and a2 == get(h2,b2,j+l+k,2*l+j+k):
                return True
    return False

N = int(input())
S = input()
mod = 1000000007
base = 37
h1 = rolling_hash(S)
b1 = setup_pw(N)
base = 401
h2 = rolling_hash(S)
b2 = setup_pw(N)
left = 1
right = N // 2
finish = False
if N <= 26:
    s = set(list(S))
    if N <= 3:
        if len(s) < N:
            print('1')
        else:
            print('0')
        finish = True
    else:
        if len(s) == N:
            print('0')
            finish = True
while finish == False:
    if left == right:
        print(left)
        finish = True
    elif right - left == 1:
        if check_bisect(right,h1,b1,h2,b2):
            print(right)
        else:
            print(left)
        finish = True
    else:
        mid = (left+right) // 2
        if check_bisect(mid,h1,b1,h2,b2):
            left = mid
        else:
            right = mid - 1
### BUGGY CODE ###

def main():
	n = int(input())
	l = [str(input()) for i in range(n)]
	ans = []
	ans_2 = []
	for i in range(n):
		if ans.count(l[i]) == 0:
			ans.append(l[i])
			ans_2.append(l.count(l[i]))
	indexes = [i for i, x in enumerate(ans_2) if x == max(ans_2)]
	ans_3 = []
	for s in indexes:
		ans_3.append(ans[s])
	ans_3.sort()


	print('\n'.join(map(str, ans_3)))


	
	
 
if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	# n,m = map(int,input().split())
	n = int(input())
	l = [str(input()) for i in range(n)]
	
	import collections

	c = collections.Counter(l)
	lc = sorted(list(c.items()), key = lambda x:x[1] , reverse = True)
	# print(lc[0][0])
	ans = []
	checker = 0
	i = 0
	while checker == 0 and i < len(lc):
		if lc[i][1] == lc[0][1]:
			ans.append(lc[i][0])
		else:
			checker += 1
		i += 1

	# keys = [k for k, v in c.items() if v == max(c.values())]
	# print(list(c.items())[0][0])
	# checker = 0
	# while checker == 0:
	# 	if c.items() == max(c.values()):
	ans.sort()
	print('\n'.join(map(str, ans)))

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

s = input()
while(s != s.replace("ST", "")):
    s = s.replace("ST", "")
print(len(s))

### FIXED CODE ###

s = input()
cnt = 0
t = 0
for c in s:
    if(c == "S"):
        cnt += 1
    else: # T
        if(cnt > 0):
            cnt -= 1
        else:
            t += 1
print(cnt + t)
### BUGGY CODE ###

MOD = 10**9 + 7

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


k = int(input())
s = input()
n = len(s)
ans = 0

fact, inv = prepare(10**6, MOD)
for i in range(k+1):
    c25 = 1
    for j in range(i):
        c25 *= 25
        c25 % MOD
    f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
    c25 *= f
    c25 %= MOD
    c26 = 1
    for h in range(k-i):
        c26 *= 26
        c26 % MOD
    ans += (c25 * c26 % MOD)
    ans %= MOD
print(ans)


### FIXED CODE ###

MOD = 10**9 + 7

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs


k = int(input())
s = input()
n = len(s)
ans = 0

l = k+n + 3
 
a25 = [1]
for i in range(l):
    a25.append((a25[-1] * 25) % MOD)
a26 = [1]
for i in range(l):
    a26.append((a26[-1] * 26) % MOD)

fact, inv = prepare(n+k, MOD)
for i in range(k+1):
    c25 = a25[i]
    f = fact[i+n-1] * inv[i] % MOD * inv[n-1] % MOD
    c25 *= f
    c25 %= MOD

    c26 = a26[k-i]
    ans += (c25 * c26 % MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

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

cnt = 0
for a in range(N-2):
  for b in range(a+1,N-1):
    for c in range(b+1,N):
      if L[c] < L[a] + L[b]:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

def binary_search(a,b):
  top = N
  bottom = b
  c = (top + bottom)//2
  while top - bottom > 1:
    #print(a,b,":",top,bottom,c)
    if L[c] < L[a] + L[b]:
      bottom = c
    else:
      top = c
    c = (top + bottom)//2
  return top - 1

cnt = 0
for a in range(N-2):
  for b in range(a+1,N-1):
    cnt += binary_search(a,b) - b

print(cnt)
### BUGGY CODE ###

N = int(input())
S = input()
P = [0]*N
for T in range(0,N):
    P[T] = S[:T].count('W')+S[(T+1):].count('E')
print(min(P))

### FIXED CODE ###

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

EP = [0]*(N+1)
WP = [0]*(N+1)
CP = [0]*N
for T in range(0,N):
    EP[N-T-1] = EP[N-T]+(S[N-1-T]=='E')
    WP[T+1] = WP[T]+(S[T]=='W')
for T in range(0,N):
    CP[T] = EP[T+1]+WP[T]
print(min(CP))
### BUGGY CODE ###

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

rn=s.count('R')
gn=s.count('G')
bn=s.count('B')

ll=len(s)
ans=0
if ll>2:
  
  for x in range(len(s)-2):
    if s[x]=='R':
      rn-=1
      ans+=gn*bn
    elif s[x]=='G':
      gn-=1
      ans+=rn*bn
    else:
      bn-=1
      ans+=gn*rn
    y=(n-1-x)//2
    for i in range(1,y+1):
      if  (not s[x]==s[x+i]) & (not s[x]==s[x+i+i]) & (not s[x+i]==s[x+i+i]):
        ans-=1
        
  print(ans)
    
else:
  print(0)

### FIXED CODE ###

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

rn=s.count('R')
gn=s.count('G')
bn=n-rn-gn

ans=bn*gn*rn
if n>2:
  
  for x in range(n-2):
    
    y=(n-1-x)//2
    for i in range(1,y+1):
      if  (not s[x]==s[x+i]) & (not s[x]==s[x+i+i]) & (not s[x+i]==s[x+i+i]):
        ans-=1
        
  print(ans)
    
else:
  print(0)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
# INF = 1<<32

def solve(N: int):
    # from functools import lru_cache
    # # abc154を参考にメモ化で出すとTLE
    # @lru_cache(None)
    # def f(n: int):
    #     if 0 <= n <=5:
    #         return n
    #     elif 6 <= n < 10:
    #         return 10-n+1

    #     q, r = divmod(n, 10)
    #     # print(q, r)
    #     return min(
    #         f(q)+r,
    #         f(q+1)+10-r
    #     )
    # print(f(N))

    # N=36を考える
    l = list(map(int, list(str(N))))
    dp = 0,1
    for i in l:
        # a = f(3), f(36)
        a = min(dp[0]+i, dp[1]+10-i)
        # b = f(4), f(40)
        b = min(dp[0]+i+1, dp[1]+10-(i+1))
        dp = a, b

    print(dp[0])
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
# INF = 1<<32

def solve(N: "List[int]"):
    # N=36を考える
    # l = list(map(int, list(str(N))))
    dp = 0,1
    for i in N:
        # a = f(3), f(36)
        a = min(dp[0]+i, dp[1]+10-i)
        # b = f(4), f(40)
        b = min(dp[0]+i+1, dp[1]+10-(i+1))
        dp = a, b

    print(dp[0])
    return



def main():
    stdin = open(0)
    N = [int(x) for x in stdin.read().rstrip()]
    solve(N)

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

N = int(input())

ans = 0
ctable = [[-1 for _ in range(10)] for _ in range(10)]

def c(x, y):
    cnt = 0
    for i in range(1, N+1):
        if int(str(i)[0]) == x and int(str(i)[-1]) == y:
            cnt += 1
    return cnt

for i in range(10):
    for j in range(10):
        ctable[i][j] = c(i, j)

for i in range(10):
    for j in range(10):
        ans += ctable[i][j] * ctable[j][i]

print(ans)


### FIXED CODE ###

N = int(input())

cnt = 0
for i in range(1, N+1):
    first = str(i)[0]
    last = str(i)[-1]
    if first == last:
        cnt += 1
    if last != '0':
        if len(str(N)) == 2:
            if int(last+first) <= N:
                cnt += 1
        if len(str(N)) >= 3:
            for j in range(len(str(N))-2):
                cnt += 10**j
            middle = str(N)[1:-1]
            if last < str(N)[0]:
                cnt += 10**(len(str(N))-2)
            elif last == str(N)[0]:
                if first > str(N)[-1]:
                    cnt += int(middle)
                else:
                    cnt += int(middle) + 1

print(cnt)
### BUGGY CODE ###

N = int(input())

i = 2
while True:
    if i%2 == 0 and i %N == 0:
        break
    i+=1

print(i)

### FIXED CODE ###

n = int(input())

if n %2 == 0:
    print(n)
else:
    print(n*2)
### BUGGY CODE ###

S=input()
N=len(S)
dp=[[0]*2019 for _ in range(N)]
dp[0][int(S[0])]=1
for i in range(1, N):
    for j in range(2019):
        dp[i][(j*10+int(S[i]))%2019]+=dp[i-1][j]
    dp[i][int(S[i])]=1
print(sum([dp[i][0] for i in range(N)]))

### FIXED CODE ###

MOD=2019
S=input()
N=len(S)
nums=[0]*N
nums[-1]=int(S[-1])%MOD
for i in range(-2, -N-1, -1):
  nums[i]=(int(S[i])*pow(10, -(i+1), MOD)+nums[i+1])%MOD

a=[0]*2019
for i in range(N):
  a[nums[i]]+=1
  
print(a[0]+sum([(a[i]*(a[i]-1))//2 for i in range(2019)]))
### BUGGY CODE ###

import sys  
input = sys.stdin.readline
import numpy as np
 
N, M = list(map(int, input().split()))
 
A = list(map(int, input().split()))

card = []
for i in range(M):
    b, c = list(map(int, input().split()))
    x = [c]*b
    card.extend(x)
 
A.extend(card)
A.sort()
    
 
print(sum(A[-N:]))

### FIXED CODE ###

import sys  
input = sys.stdin.readline
 
N, M = list(map(int, input().split()))
 
A = list(map(int, input().split()))



BC = []
for i in range(M):
    b, c = list(map(int, input().split()))
    BC.append([b, c])

BC=sorted(BC, reverse=True, key=lambda x:x[1])

cnt = 0
com = []
for b, c in BC:
    cnt += b
    if cnt > N:
        add = N-cnt+b
        com.extend([c]*add)
        break
    else:
        x = [c]*b 
        com.extend(x)
A.sort()   
num = -1
for k in range(N):
    if k == len(com):
        num = k
        break
    if A[k] > com[k]:
        num = k
        break

if num == -1:
    print(sum(com))
else:
    print(sum(com[:num])+sum(A[num:]))
### BUGGY CODE ###

N,A,B=map(int,input().split())
n=0
S=''
flag=False
while True:
    for i in range(A):
        S+='b'
        n+=1
        if n==N:
            flag=True
            break
    if flag:
        break
    
    for i in range(B):
        S+='r'
        n+=1
        if n==N:
            flag=True
            break
    if flag:
        break
    
cnt=0
for i in S:
    if i=='b':
        cnt+=1

print(cnt)

### FIXED CODE ###

N,A,B=map(int,input().split())
cycle=A+B
a=N//cycle
b=N%cycle
if b>A:
    b=A
cnt=a*A+b
print(cnt)
### BUGGY CODE ###

from collections import deque

def bfs(maze):
    h = len(maze)
    w = len(maze[0])
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    d = deque()
    
    last =[-1, -1]
    for y in range(h):
        for x in range(w):
            if maze[y][x] == '#':
                d.append([y, x])
                visited[y][x] = 0
                last[0] = y
                last[1] = x
    
    while d:
        y, x = d.popleft()
        
        for l, k in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            new_y, new_x = y + l, x + k
            
            if new_y < 0 or h <= new_y or new_x < 0 or w <= new_x:
                continue
            elif visited[new_y][new_x] != -1:
                continue
            elif maze[new_y][new_x] == '#':
                continue
            
            d.append([new_y, new_x])
            visited[new_y][new_x] = visited[y][x] + 1

        last[0] = y
        last[1] = x
        
    ''' 確認用
    print(last)
    for i in range(h):
        print(visited[i])
    '''
        
    return visited[last[0]][last[1]]

if __name__ == "__main__":
    h, w = map(int, input().split())
    maze = []
    for i in range(h):
        maze.append(list(input()))
    ''' 確認用
    for i in range(h):
        print(maze[i])
    '''
    
    print(bfs(maze))

### FIXED CODE ###

from collections import deque

def bfs(maze):
    h = len(maze)
    w = len(maze[0])
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    d = deque()
    
    last =[-1, -1]
    for y in range(h):
        for x in range(w):
            if maze[y][x] == '#':
                d.append([y, x])
                visited[y][x] = 0
                last[0] = y
                last[1] = x
    
    while d:
        y, x = d.popleft()
        
        for l, k in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            new_y, new_x = y + l, x + k
            
            if new_y < 0 or h <= new_y or new_x < 0 or w <= new_x:
                continue
            elif visited[new_y][new_x] != -1:
                continue
            elif maze[new_y][new_x] == '#':
                continue
            
            d.append([new_y, new_x])
            visited[new_y][new_x] = visited[y][x] + 1

        last[0] = y
        last[1] = x
        
    ''' 確認用
    print(last)
    for i in range(h):
        print(visited[i])
    '''
        
    return visited[last[0]][last[1]]

if __name__ == "__main__":
    h, w = map(int, input().split())
    maze = []
    for i in range(h):
        maze.append(list(input()))
    ''' 確認用
    for i in range(h):
        print(maze[i])
    '''
    
    print(bfs(maze))
### BUGGY CODE ###

#coding:utf-8

def main():
    n, q = map(int, input().split())
    s = input()
    slist = list(s)
    point = []
    for i in range(q):
        c = 0
        l, r = map(int, input().split())
        for j in range(l-1,r-1):
            if slist[j] == 'A':
                if slist[j+1] == 'C':
                    c += 1
                else:
                    pass
            else:
                pass
        point.append(c)

    for k in range(len(point)):
        print(point[k])


if __name__ == "__main__":
    main()

### FIXED CODE ###

#coding-utf:8

def main():
    n, q = map(int, input().split())
    s = input()
    t = [0] * (n+1)
    for i in range(n):
        if s[i : i+2] == 'AC':
            x = 1
        else:
            x = 0
        t[i+1] = t[i] + x
        x = 0

    for j in range(q):
        l, r = map(int, input().split())
        print(t[r-1] - t[l-1])

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

N = int(input())

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

A = sorted(A)[0:2]

INF = 10 ** 9

for i in range(0,INF):
	A[1] = A[1] - A[0]
	if A[1] < A[0]:
		A[1],A[0] = A[0],A[1]
	if A[0] < 0:
		break
	
print(A[1])

### FIXED CODE ###

import fractions
from functools import reduce

def gcd(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())

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

print(gcd(A))
### BUGGY CODE ###

from collections import deque
import sys

INF = 10 ** 8

H, W = map(int,input().split())
CH, CW = map(int,input().split())
DH, DW = map(int,input().split())

S = []
for _ in range(H):
    S.append(list(input()))

d = [[INF for i in range(W)] for j in range(H)]

Q = deque([[CH-1, CW-1, 0]])
d[CH - 1][CW - 1] = 0

while len(Q) != 0:
    x, y, cnt = Q.popleft()
    
    d[x][y] = cnt
    
    if x == DH - 1 and y == DW - 1:
        print(cnt)
        sys.exit()
    
    for tx in range(-2, 3):
        for ty in range(-2, 3):
            nx = x + tx
            ny = y + ty
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "." and d[nx][ny] == INF:
                if abs(tx)+abs(ty) == 1:
                    Q.appendleft([nx, ny, cnt])
                else:
                    Q.append([nx, ny, cnt + 1])

print(-1)

### FIXED CODE ###

from collections import deque
import sys

INF = 10 ** 8

H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
MAP = []
for _ in range(H):
    MAP.append(list(input()))
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]
tx_y = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]

Q = deque()
Q.append([C[0]-1, C[1]-1, 0])

while len(Q) != 0:
    x, y, cnt = Q.popleft()
    
    if x == D[0]-1 and y == D[1]-1:
        print(cnt)
        sys.exit()
    
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt:
            d[nx][ny] = cnt
            Q.appendleft([nx, ny, cnt])
    
    for i, j in tx_y:
        nx = x + i
        ny = y + j
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt+1:
            d[nx][ny] = cnt+1
            Q.append([nx, ny, cnt+1])

print(-1)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
res = 0
for i in range(N):
    if P[i] == N:
        continue
    l1 = i - 1
    r1 =  i + 1
    while l1 >= 0 and P[l1] < P[i]:
        l1 -= 1
    while r1 < N and P[r1] < P[i]:
        r1 += 1
    l2 = l1 - 1
    r2 = r1 + 1
    while l2 >= 0 and P[l2] < P[i]:
        l2 -= 1
    while r2 < N and P[r2] < P[i]:
        r2 += 1
    if l1 == - 1:
        res += P[i]*(i + 1)*(r2 - r1)
    elif r1 == N:
        res += P[i]*(l1 - l2)*(N - i)
    else:
        res += P[i]*((l1 - l2)*(r1 - i) + (i - l1)*(r2 - r1))
print(res)

### FIXED CODE ###

import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

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

N = int(input())
s= [input() for i in range(N)]
ans=0
for i in range(N):
        for k in range(i+1,N):
                A=list(s[i])
                for j in list(s[k]):
                        if j in A:
                                A.remove(j)
                        else:
                                break
                if len(A) == 0:
                        ans += 1

print(ans)


### FIXED CODE ###

import math
def cmb(n, r):
        if r > n: 
                return 0
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


import collections
N = int(input())
s= [input() for i in range(N)]
ans=0
#各文字列文字列をソート
s=list(map(sorted,s))

s.sort()        #リストをソート
s=list(map(''.join,s))  #リストになっていたものを文字列に変換
clist = collections.Counter(s) #リスト内の各要素の数を数え上げ
kaisu=list(clist.values())

for i in kaisu:
        ans += cmb(i,2)

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

#!/usr/bin/env python3
N = int(input())

s = [] * 2
print(0, flush=True)
s[0] = input()
if s[0] == 'Vacant':
    exit()

l, r = 0, N
while r - l > 2:
    m = (l + r) // 2
    print(m, flush=True)
    s[1] = input()
    if s[1] != 'Vacant':
        exit()

    if s[0] == s[1]:
        l, r = (l, m) if (m - l) % 2 == 1 else (m, r)
    else:
        l, r = (m, r) if (m - l) % 2 == 1 else (l, m)
    s[0] = s[1]
print(l + 1, flush=True)


### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())

print(0, flush=True)
w0 = input()
if w0 == 'Vacant':
    exit()

l, r = 0, N
while True:
    m = (l + r) // 2
    print(m, flush=True)
    w1 = input()
    if w1 == 'Vacant':
        break
    if m % 2 == (w0 != w1):
        l = m
    else:
        r = m
### BUGGY CODE ###

n = int(input())
nums = list(map(int,input().split(" ")))
nums.sort()
total = 0
for i in range(n):
    for j in range(i+1,n):
        k = j+1
        while k < n and nums[k] < nums[i] + nums[j]:
            k+=1    
        total += k-j -1 
print(total)

### FIXED CODE ###

n = int(input())
nums = list(map(int,input().split(" ")))
nums.sort()
total = 0
for i in range(n-1,-1,-1):
    l = 0
    r = i-1
    while l < r:
        if nums[l] + nums[r] > nums[i]:
            total += r - l
            r -= 1
        else:
            l += 1
print(total)
### BUGGY CODE ###

def bisect_left_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番左側のidxとなる。
    '''
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok
def main2():
    n = int(input())
    l=[int(i) for i in input().split()]
    l.sort(reverse = True)
    res = 0
    for i in range(n-1):
        for j in range(i+1, n-1):
            #index がj以降で　k < c を満たすcで一番小さいc'を探す
            #index(c')-j - 1が三角形の条件を満たす
            nibu = l[j+1:]
            k = max(l[i]-l[j],l[j]-l[i])
            left=bisect_left_reverse(nibu,k)
            res += left
    print(res)

if __name__ == '__main__':
    main2()


### FIXED CODE ###

import bisect
def bisect_right_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番右側のidx+1となる。
    '''
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok
def bisect_left_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番左側のidxとなる。
    '''
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok
def main2():
    n = int(input())
    l=[int(i) for i in input().split()]
    l.sort(reverse = True)
    res = 0
    for i in range(n-1):
        for j in range(i+1, n-1):
            #index がj以降で　k < c を満たすcで一番小さいc'を探す
            #index(c')-j - 1が三角形の条件を満たす
            nibu = l[j+1:]
            k = max(l[i]-l[j],l[j]-l[i])
            left=bisect_left_reverse(nibu,k)
            res += left
    print(res)

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

import itertools
N = int(input())
L = list(map(int,input().split()))
L.sort()
tri = list(itertools.combinations(L,3))
cnt = 0
for a,b,c in tri:
    if a < (b+c) and b < (c+a) and c < (a+b):
        cnt += 1
print(cnt)
    

### FIXED CODE ###

import bisect
n=int(input())
l = list(map(int,input().split()))
l.sort()
うんち = 0
for i in range(1,n):
    for j in range(i):
        p = l[i] + l[j]
        q = bisect.bisect_left(l,p)
        うんち += q-i-1
print(うんち)