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

n = int(input())
print(0)
syo = 0
s = input()
if s == "Vacant":
  exit()
maes = s
dai = n-1
print(n-1)
s = input()
dais = s
if s == "Vacant":
  exit()
while True:
  mid = (dai+syo)//2
  print(mid)
  s = input()
  if s == "Vacant":
    exit()
  if ((mid - syo)%2 == 0 and s != syos) or ((mid - syo)%2 == 1 and s == syos):
    dai = mid
    dais = s
  else:
    syo = mid
    syos = s

### FIXED CODE ###

n = int(input())
print(0, flush=True)
syo = 0
s = input()
if s == "Vacant":
  exit()
syos = s
dai = n-1
print(n-1, flush=True)
s = input()
dais = s
if s == "Vacant":
  exit()
for _ in range(18):
  mid = (dai+syo)//2
  print(mid, flush=True)
  s = input()
  if s == "Vacant":
    exit()
  if ((mid - syo)%2 == 0 and s != syos) or ((mid - syo)%2 == 1 and s == syos):
    dai = mid
    dais = s
  else:
    syo = mid
    syos = s
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1,N):
    for j in range(1,i+1):
        if i % j == 0:
            ans += 1
            #print(i,j)
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1,N):
    #print((N-0.5)//i)
    ans += (N-1) // i
print(ans)
### BUGGY CODE ###

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

dp = [0]*n
dp[0] = 0

for i in range(1,n):
    dp[i] = dp[i-1] + abs(h[i-1]-h[i])

    for j in range(2,k+1):
        if (i-j)>=0:
            dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

# print(dp)
print(dp[n-1])

### FIXED CODE ###

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

dp = [0]*n
dp[0] = 0

for i in range(1,n):
    dp[i] = dp[i-1] + abs(h[i-1]-h[i])

    for j in range(2,k+1):
        if (i-j)>=0:
            dp[i] = min(dp[i], dp[i-j] + abs(h[i]-h[i-j]))

# print(dp)
print(dp[n-1])
### BUGGY CODE ###

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

n, x = mygets()
a = mygets()

b1 = a.copy()
b2 = a.copy()

ans = sum(a)

for i in range(1, n):
    for j in range(n):
        b2[j] = min(a[j], b1[(j + n - 1) % n])
    ans = min(ans, sum(b2) + i * x)
    b1, b2 = b2, b1

print(ans)

### FIXED CODE ###

def mygets():
    return list(map(int, input().strip().split(' ')))

n, x = mygets()
a = mygets()

b1 = a

ans = sum(a)

def f(k, u):
    j = k - 1
    if j < 0:
        j = n - 1
    w = b1[j]
    if u < w:
        return u
    return w

for i in range(1, n):
    b2 = [f(k, u) for k, u in enumerate(a)]
    ans = min(ans, sum(b2) + i * x)
    b1 = b2

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

import sys
import heapq


def dfs(u,s,target, vs):
    vs[u] = 1
    if(u == target):
        global h
        heapq.heappush(h,s)
        return
    for j in range(e):
        if(e_1[j] == u):
            if(vs[e_2[j]] != 1):
                count = s + e_w[j]
                print(s,e_2[j],vs)
                dfs(e_2[j],count,target,vs[0:])



v,e,r=map(int, input().split());

e_1=[0]*e;
e_2=[0]*e;
e_w=[0]*e;

for i in range(e):
    e_1[i], e_2[i], e_w[i] = map(int, input().split());

v_q=[];

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
heapq.heappush(v_q,(0,r))
heapq.heappush(v_q,(INF,0))
while(True):
    cost,u = heapq.heappop(v_q)
    if(cost == INF):
        break
    if(cost > d[u]):
        continue
    for j in range(e):
        if(u == e_1[j]):
            alt = cost+e_w[j]
            if(d[e_2[j]] > alt):
                d[e_2[j]] = alt
                heapq.heappush(v_q,(alt,e_2[j]))

for i in range(v):
    if(d[i] != INF):
        print(d[i])
    else:
        print("INF")





### FIXED CODE ###

import sys
from collections import deque

v,e,r=map(int, input().split());

edge_info=[0]*v;
for i in range(v):
    edge_info[i] = []

for i in range(e):
    e1, e2, w = map(int, input().split());
    edge_info[e1].append((e2,w))

v_q=deque();

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
v_q.append((0,r))
while(len(v_q) != 0):
    cost,u = v_q.popleft()
    if(cost > d[u]):
        continue
    for j in range(len(edge_info[u])):
        e2,w = edge_info[u][j]
        alt = cost+w
        if(d[e2] > alt):
            d[e2] = alt
            v_q.append((alt,e2))

for i in range(v):
    if(d[i] != INF):
        print(d[i])
    else:
        print("INF")
### BUGGY CODE ###

import math
N=int(input())
f=[0]*N
for i in range(N):
    for j in range(int(math.sqrt(i+1))):
        for k in range(int(math.sqrt(i+1))):
            for l in range(int(math.sqrt(i+1))):
                if (j+1)*(j+1)+(k+1)*(k+1)+(l+1)*(l+1)+(j+1)*(k+1)+(k+1)*(l+1)+(l+1)*(j+1)==(i+1):
                    f[i]=f[i]+1

for i in range(N):
    print(f[i])


### FIXED CODE ###

import math
N=int(input())
f=[0]*(10050)
for j in range(int(math.sqrt(N))):
    for k in range(int(math.sqrt(N))):
        for l in range(int(math.sqrt(N))):
            i=(j+1)*(j+1)+(k+1)*(k+1)+(l+1)*(l+1)+(j+1)*(k+1)+(k+1)*(l+1)+(l+1)*(j+1)
            if i<10050:
                f[i]=f[i]+1

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

N, M = map(int, input().split())
H = list(map(int, input().split()))
dai = [list(map(int, input().split())) for i in range(M)]
plus = [i for i in range(N)]
cnt = 0

for i in range(0, N):
    for a, b in dai:
        if i+1 == a:
            if H[a - 1] > H[b - 1]:
                continue
            else:
                plus[i] = -1
                break
        if i+1 == b:
            if H[b - 1] > H[a - 1]:
                continue
            else:
                plus[i] = -1
                break
print(len(set(plus))-1)


### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
dai = [list(map(int, input().split())) for i in range(M)]
plus = [i for i in range(N)]


for a, b in dai:
    if H[a - 1] > H[b - 1]:
        plus[b-1] = -1
        continue
    else:
        plus[a-1] = -1
    if H[b - 1] > H[a - 1]:
        plus[a-1] = -1
        continue
    else:
        plus[b-1] = -1
print(len(set(plus))-1)
### BUGGY CODE ###

#!/usr/bin/env python3
#A
import re

a,b = map(int,input().split())

c = [list(map(str,input().split()))for i in range(a)]
d = [[0 for j in range(b)]  for i in range(a)]

for i in range(a):#初期のリスト設定
    for j in range(b):
        if c[i][0][j] == '#':
            d[i][j] = 1

def change(save,d):
    for i in save:
        d[i[0]][i[1]] = 1

count = 0
for k in range(a*b):
    save = []
    for i in range(a):
        for j in range(b):
            if d[i][j] == 1:
                if i != 0 and d[i-1][j] == 0:
                        save.append((i-1,j))
                if j != 0 and d[i][j-1] == 0:
                        save.append((i,j-1))
                if i != a-1 and d[i+1][j] == 0:
                        save.append((i+1,j))
                if j != b-1 and d[i][j+1] == 0:
                        save.append((i,j+1))

    change(save,d)
    if len(save) == 0:
        break;
    count += 1
print(count)

### FIXED CODE ###

#!/usr/bin/env python3
#AGC33 A

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
maze = [list(input()) for _ in range(h)]
check = [[True]*w for _ in range(h)]
dx,dy = [0,1,0,-1],[1,0,-1,0]
que = deque()
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            check[i][j] = False
            que.append((j,i))
res = 0
while que:
    que2 = deque(que)
    que = deque()
    flg = False
    while que2:
        x,y = que2.popleft()
        for i in range(4):
            nx,ny = x + dx[i], y + dy[i]
            if 0 <= nx < w and 0 <= ny < h:
                if check[ny][nx]:
                    check[ny][nx] = False
                    que.append((nx,ny))
                    flg = True
    if flg:
        res += 1
print(res)
### BUGGY CODE ###

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


arr = get_sieve_of_eratosthenes(100000)

arr_2 = []

for i in range(1, len(arr)):
    if (arr[i] + 1) / 2 in arr:
        arr_2.append(arr[i])

Q = int(input())
for q in range(Q):
    l, r = map(int, input().split())
    left_ind = bisect.bisect_left(arr_2, l)
    right_ind = bisect.bisect_right(arr_2, r)
    print(right_ind - left_ind)

### FIXED CODE ###

import bisect
import math

def prime(n):
    for j in range(2, int(math.sqrt(n) + 1)):
        if n % j == 0:
            return False
    return True

lis = []
for i in range(3, 100000, 2):
    if prime(i) and prime((i + 1) / 2):
        lis.append(i)

Q = int(input())
for q in range(Q):
    l, r = map(int, input().split())
    left_ind = bisect.bisect_left(lis, l)
    right_ind = bisect.bisect_right(lis, r)
    print(right_ind - left_ind)
### BUGGY CODE ###

N,K=map(int,input().split())
S=list(map(int,input().split()))

maxSKsum=0
startSindex=0

for i in range(len(S)):  #ここがrange(len(S)-K)ではダメないのがわからない・・・
    tempSKsum=sum(S[i:i+K])
    if maxSKsum<tempSKsum:
        maxSKsum=tempSKsum
        startSindex=i
    else:
        pass

EVlist=[]
for s in range(K):
    tempEV=S[startSindex+s]*(S[startSindex+s]+1)/2/S[startSindex+s]
    EVlist.append(tempEV)

print(sum(EVlist))

### FIXED CODE ###

N,K=map(int,input().split())
_=input().split()
S=[]
for s in _:
    S.append((int(s)+1)/2) #初めから期待値で配列作成

maxsum=sum(S[0:K])
tempsum=maxsum

for i in range(N-K):
    tempsum=tempsum-S[i]+S[i+K]
    if maxsum<tempsum:
        maxsum=tempsum
    else:
        pass

print(maxsum)
### BUGGY CODE ###

import math

def cmb(n, r):
  if n == r:
    return 1
  return math.factorial(n % (10**9+7)) // math.factorial((n-r) % (10**+7)) // math.factorial(r % (10**9+7))

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

for i in range(K):
  C = (cmb(K-1, i) * cmb((N-K+1), i+1)) % (10 ** 9 + 7)
  print(C)

### FIXED CODE ###

import math

def cmb(n, r):
  if n == r:
    return 1
  return math.factorial(n) // math.factorial(n-r) // math.factorial(r)

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

for i in range(K):
  if (N-K+1) < i + 1:
    print(0)
  else:
  	C = (cmb(K-1, i) * cmb((N-K+1), i+1)) % (10 ** 9 + 7)
  	print(C)
### BUGGY CODE ###

import sys
s = str(input())
p = len(s)
new = []
if p == 1:
    print("0")
    sys.exit()
while True:
    for i in range(len(s)-1):
        if i == len(s) - 2:
            if s[i] != s[i+1]:
                s = s[:i] + s[i+2:]
                print(p-len(s))
                sys.exit()
            else:
                print(p-len(s))
                sys.exit()
        elif s[i] != s[i+1]:
            s = s[:i] + s[i+2:]
            break

        
        

### FIXED CODE ###

s = str(input())
ze = 0
on = 0
for i in range(len(s)):
    if s[i] == "0":
        ze += 1
    else:
        on += 1
print(len(s)-max(ze,on)+min(ze,on))
### BUGGY CODE ###

from collections import deque
N = int(input())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    edge[a].append([b, c])
    edge[b].append([a, c])


def BFS(x, y):
    visited = [False for _ in range(N+1)]
    next_N = [False for _ in range(N+1)]
    INF = float('inf')
    dest = [INF for _ in range(N+1)]
    d = deque()
    visited[x] = True
    dest[x] = 0
    for B, C in edge[x]:
        d.append([B, C])
        next_N[B] = True
        dest[B] = dest[x] + C
    while d:
        now = d.popleft()
        visited[now[0]] = True
        for B, C in edge[now[0]]:
            if visited[B] == False and next_N[B] == False:
                d.append([B, C])
                next_N[B] = True
                dest[B] = dest[now[0]] + C
    return dest[y]

Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]
for X, Y in xy:
    print(BFS(X, K) + BFS(K, Y))


### FIXED CODE ###

from collections import deque
N = int(input())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    edge[a].append([b, c])
    edge[b].append([a, c])


def BFS(x):
    visited = [False for _ in range(N+1)]
    next_N = [False for _ in range(N+1)]
    INF = float('inf')
    dest = [INF for _ in range(N+1)]
    d = deque()
    visited[x] = True
    dest[x] = 0
    for B, C in edge[x]:
        d.append([B, C])
        next_N[B] = True
        dest[B] = dest[x] + C
    while d:
        now = d.popleft()
        visited[now[0]] = True
        for B, C in edge[now[0]]:
            if visited[B] == False and next_N[B] == False:
                d.append([B, C])
                next_N[B] = True
                dest[B] = dest[now[0]] + C
    return dest

Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]
DEST = BFS(K)
for X, Y in xy:
    print(DEST[X] + DEST[Y])
### BUGGY CODE ###

def main():
  n = int(input())
  s = input()
  s1 = []
  s2 = []
  s3 = []
  ss = [("R",s.count("R")),("G",s.count("G")),("B",s.count("B"))]
  ss = sorted(ss,key=lambda x:x[1])
  ans = ss[0][1]*ss[1][1]*ss[2][1]
  for i in range(n):
    if s[i]==ss[2][0]:
      s3.append(i)
    elif s[i]==ss[1][0]:
      s2.append(i)
    elif s[i]==ss[0][0]:
      s1.append(i)
      
  for i in s1:
    for j in s2:
      if i*2-j in s3:
        ans -= 1
      if j*2-i in s3:
        ans -= 1
      if (i+j)%2==0 and (i+j)/2 in s3:
        ans -= 1
  print(ans)
main()

### FIXED CODE ###

def main():
  n = int(input())
  s = input()
  ans = s.count("R")*s.count("G")*s.count("B")
  for i in range(n-2):
    for j in range(i+1,n-1):
      k = j + j - i
      if k >= n:
        break
      elif s[i] != s[j] and s[i] != s[k] and s[k] != s[j]:
        ans -=1
  print(ans)
main()
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ans = 0

for i in range(len(A)):
  for j in range(i+1, len(A)):
    ans += A[i]*A[j]
    if ans > 10**9+7:
      ans %= 10**9+7
print(ans)


### FIXED CODE ###

import numpy as np

N = int(input())
A = [int(i) for i in input().split()]
sum = 0
for x in A:
  sum += x
  sum %= (10**9+7)

sum2 = 0
for x in A:
  sum2 += x*x
  sum2 %= (10**9+7)

ans = (sum**2 - sum2) % (10**9+7)
if ans < 0:
  ans += (10**9+7)
ans *= int((10**9+7+1)/2) 
ans %= (10**9+7)
print(int(ans))
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
SUM = 0
DIV = 10**9 + 7

for i in range(1,N):
    for j in range(i+1,N+1):
        XOR = A[i-1]^A[j-1]#XOR
        SUM = SUM + XOR
if SUM < DIV:
    print(SUM)
else:
    print(SUM%DIV)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
p=10**9 + 7 
l=[0]*60
for i in range(60):
    for j in a:
        l[i]+=(j>>i)&1
    ans=(ans + (2**i) * l[i] * (n-l[i]))%p
print(ans)
### BUGGY CODE ###

"""
01BFS: ステップ数が多ければ後ろに持っていく
"""
from collections import deque
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
maze = [list(input()) for _ in range(H)]

que = deque([(Ch-1,Cw-1,0)])
adjectns = [(1,0),(0,1),(-1,0),(0,-1)]
for _ in range(100000000):
    if not que:
        break
    h,w,step = que.popleft()
    if h == Dh-1 and w == Dw-1:
        print(step)
        exit()
    else:
        if maze[h][w] == ".":
            maze[h][w] = step
            for a,b in adjectns:
                x = h + a
                y = w + b
                if 0<=x<H and 0<=y<W:
                    que.appendleft((x,y,step))
            for i in range(-2,3):
                for j in range(-2,3):
                    x = h+i
                    y = w+j
                    if 0<=x<H and 0<=y<W:
                        que.append((x,y,step+1))
print(-1)



### FIXED CODE ###

"""
dp[i][j] => マスi,jに到達するのに必要なワープ回数。
近隣5*5のマスから
"""


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

    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1
    maze = [list(input()) for _ in range(H)]

    que = deque([(Ch,Cw,0)])
    nxQue = deque([])
    adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
    INF = 10**13
    for _ in range(INF):
        if not que:
            if nxQue:
                que = nxQue
                nxQue = deque([])
                continue
            else:
                break
        h,w,worp = que.popleft()
        if maze[h][w] == "#" or (maze[h][w]!="." and maze[h][w] <= worp):
            continue
        else:
            maze[h][w] = worp
            for a,b in adjecents:
                nxh,nxw = h+a,w+b
                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw]>worp):
                    que.append((nxh,nxw,worp))
                elif 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]=="#":
                    if b == 0:
                        for i in range(a,a*3,a):
                            for j in range(-2,3,1):
                                nxh,nxw = h+i,w+j
                                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw] > worp+1):
                                    nxQue.append((nxh,nxw,worp+1))
                    else:
                        for i in range(-2,3,1):
                            for j in range(b,b*3,b):
                                nxh,nxw = h+i,w+j
                                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw] > worp+1):
                                    nxQue.append((nxh,nxw,worp+1))
    
    if maze[Dh][Dw] == "#" or maze[Dh][Dw] == ".":
        print(-1)
    else:
        print(maze[Dh][Dw])
main()
### BUGGY CODE ###

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


mod = 10**9 + 7

ans = 0
for i in range(61):
    zero = 0
    one = 0
    for a_ in a:
        if (a_ >> i) & 1:
            one += 1
        else:
            zero += 1
    ans += one * zero * pow(2, i, mod) % mod
    ans %= mod

print(ans)

### FIXED CODE ###

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


mod = 10**9 + 7

ans = 0
for i in range(61):
    zero = 0
    one = 0
    for a_ in a:
        if (a_ >> i) & 1:
            one += 1
        else:
            zero += 1
    ans += one * zero * pow(2, i, mod) % mod
    ans %= mod

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

from collections import Counter
N = int(input())
S = [input() for i in range(N)]
S = dict(Counter(S))
T = list(S.keys())
U = list(S.values())
U = [j for j, k in enumerate(U) if k == max(U)]
Ans = []
for u in U:
    Ans.append(T[u])
Ans = sorted(Ans)
for ans in Ans:
    print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
S = [input() for _ in range(n)]

poll = Counter(S)
max_c = max(list(poll.values()))
ans = [k for k in poll.keys() if poll[k] == max_c]
ans.sort()
for a in ans:
     print(a)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
ss = [sorted(s[i]) for i in range(n)]
dic = [''.join(ss[i]) for i in range(n)]
key = [i for i in set(dic) if dic.count(i) > 1]
cnt = 0
for i in key:
    a = dic.count(i)-1
    cnt += (a * (a+1))/2
print(int(cnt))


### FIXED CODE ###

n = int(input())
s = {}
cnt = 0
for i in range(n):
    j = ''.join(sorted(input()))
    if j in s:
        s[j] += 1
    else:
        s[j] = 0
    cnt += s[j]
print(int(cnt))
### BUGGY CODE ###

IN = list(map(int, input().split()))
N, K = IN[0], IN[1]
P = list(map(int, input().split()))
C = list(map(int, input().split()))

maxsc = -1*10**9
init = True
for i in range(1, N+1):
    pos, score = i, 0
    for st in range(K):
        score += C[pos-1]
        pos = P[pos-1]
        maxsc = max(maxsc, score)
print (maxsc)


### FIXED CODE ###


IN = list(map(int, input().split()))
N, K = IN[0], IN[1]
P = [None] + list(map(int, input().split()))
C = [None] + list(map(int, input().split()))
MAX_N = 45000
#N = 1000
#K = 10**7
#P = [None] + [random.choice(list(itertools.chain(range(1,i), range(i+1,N)))) for i in range(1, N+1)]
#C = [None] + random.choices(range(-10**9, 10**9), k=N)

verbose = False

def cumsum(a):
    tmp = [0]*(len(a)+1)
    for i in range(1, len(a)+1): tmp[i] = a[i-1] + tmp[i-1]
    return tmp[1:]

def find_cycle(p, pos):
    cnt = 0
    steps = [0] * (MAX_N+1)
    path = [False] * (MAX_N+1)
    while True:
        steps[cnt] = pos
        path[pos] = True
        cnt += 1
        pos = p[pos]
        if path[pos]: break # found closure
    st = steps.index(pos) # start of closure
    return [steps[:st], steps[st:cnt]]


def score(steps, c):
    ret = [0]*len(steps)
    for i in range(len(steps)): ret[i] = c[steps[i]]
    return ret

maxsc = -10**9-1
done = [False] * (N+1)
for i in range(1, N+1):
    if verbose: print('entering', i)
    if done[i]: continue
    [preclosure_path, closure_path] = find_cycle(P, i)
    if verbose: print('closure found:', closure_path)
    closure_scores = score(closure_path, C)
    preclosure_scores = score(preclosure_path, C)
    closure_score = sum(closure_scores)
    preclosure_len, closure_len = len(preclosure_path), len(closure_path)

    cycles = (K-preclosure_len)//closure_len
    resid = (K-preclosure_len)%closure_len
    if cycles>=1: cycles -= 1
    abbrev = closure_score * cycles
   
    trail = preclosure_scores + closure_scores * 3
    path = preclosure_path + closure_path*3
    if verbose: print('score trail:', trail)
    if verbose: print('path:', preclosure_path + closure_path*3)
    if verbose: print('mark:', mark)
    mark = min(K, len(preclosure_path+closure_path)+resid)
    localmax = max(cumsum(trail[0:mark])) + max(0, closure_score*cycles)
    if verbose: print('localmax:', localmax, 'cycles:', cycles)
    maxsc = max(localmax, maxsc)

    if verbose: print('going greedy')
    for j in range(1, closure_len):
        if K<=mark+j: break
        target = path[j]
        if done[target]: continue
        localmax = max(cumsum(trail[j:mark+j])) + max(0, closure_score*cycles)
        maxsc = max(localmax, maxsc)
        done[target] = True
        if verbose: print('done:', target, 'with', localmax)

print(maxsc)
### BUGGY CODE ###

import numpy as np

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

lr_mat = np.zeros((m, 2))

for i in range(m):
    lr_mat[i, :] = list(map(int, input().split()))

cnt = 0
for i in range(n):
    flag = True
    for j in range(m):
        left = lr_mat[j, 0]
        right = lr_mat[j, 1]
        if not ((left <= i+1) and (i+1 <= right)):
            flag = False
    if(flag):
        cnt += 1

print(cnt)


### FIXED CODE ###

import numpy as np

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

lr_mat = np.zeros((m, 2))

for i in range(m):
    lr_mat[i, :] = list(map(int, input().split()))

left_max = max(lr_mat[:, 0])
right_min = min(lr_mat[:, 1])

cnt = 0
for i in range(1, n+1):
    if(left_max <= i) and (i <= right_min):
        cnt += 1

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

n = int(input())
l = list(map(int, input().split()))
l.sort()

count = 0
for i in range(n-1):
    for j in range(i+1, n):
        for k in range(j+1,n):
            if l[j] - l[i] < l[k] and l[k] < l[i] + l[j]:
                count += 1

print(count)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()

import bisect

count = 0
for i in range(n-1):
    for j in range(i+1, n):
            ab = l[i] + l[j]
            right = bisect.bisect(l, ab-1)
            left = j + 1
            count += (right - left)

print(count)