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

from collections import defaultdict

def sol(a,b,nu,checker):
    if a==b:
        return None,0
    loop=['R','G','B']
    for each in loop:
        if a!=each and b!=each:
            res=(checker[-1][each]-checker[nu][each])
            return each,res

n=int(input())
s=input()
#import random
#n=4000
#hoge=['R','G','B']
#s=[hoge[i%3] for i in range(n)]
#s="".join(s)
rgb_init={'R':0,'G':0,'B':0}
store=[rgb_init.copy()]
for i,v in enumerate(s):
    tmp=store[i].copy()
    tmp[v]+=1
    store.append(tmp)

ans=0
for i in range(n):
    for j in range(i+1,n):
        al,val=sol(s[i],s[j],j+1,store)
        if (al and 2*j-i<n)and s[2*j-i]==al:
            val-=1
        ans+=val
print(ans)


### FIXED CODE ###

def sol(a,b,nu,checker):
    if a==b:
        return None,0
    val={'R':0,'G':1,'B':-1}
    ev={0:'R',1:'G',-1:'B'}
    cal=(val[a]+val[b])*(-1)
    each=ev[cal]
    res=(checker[-1][each]-checker[nu][each])
    return each,res

n=int(input())
s=input()
#n=4000
#hoge=['R','G','B']
#s=[hoge[i%3] for i in range(n)]
#s="".join(s)
rgb_init={'R':0,'G':0,'B':0}
store=[rgb_init.copy() ]
for i,v in enumerate(s):
    tmp=store[i].copy()
    tmp[v]+=1
    store.append(tmp)

ans=0
for i in range(n):
    for j in range(i+1,n):
        al,val=sol(s[i],s[j],j+1,store)
        if (al and 2*j-i<n)and s[2*j-i]==al:
            val-=1
        ans+=val
print(ans)
### BUGGY CODE ###

s=input()
x,y = [int(i) for i in input().split()]

#print(s)

susumu = [0]
for i in range(len(s)):
    if s[i] == 'F':
        susumu[-1] += 1
    else:
        susumu.append(0)

#print(susumu)

syokiti = susumu[0]

susumu_NS = susumu[1::2]
susumu_EW = susumu[2::2]

x -= syokiti

#print(susumu)
#print(susumu_NS)
#print(susumu_EW)
# ＥＷの部分和でx? NSの部分和でy？

LL = len(s)+2
dp = [[0 for i in range(2*LL)] for j in range(1+len(susumu_NS))]
dp[0][LL] = 1

for j in range(len(susumu_NS)):
    #    print('j='),
    #    print(j)
    for i in range(2*LL):
    #        a=0
    #        print(i+susumu_NS[j])
        try:
            dp[j+1][i] = dp[j][i+susumu_NS[j]] | dp[j][i-susumu_NS[j]]
        except IndexError:
            if i < 0:
                dp[j+1][i] = dp[j][i+susumu_NS[j]]
            else:
                dp[j+1][i] = dp[j][i-susumu_NS[j]]

can_y = 0
if dp[len(susumu_NS)][y+LL] != 0:
    can_y = 1
#print(dp)
#print(susumu_NS)
#print(can_y)
    
#########################################
LL = len(s)+2
dp = [[0 for i in range(2*LL)] for j in range(1+len(susumu_EW))]
dp[0][LL] = 1

for j in range(len(susumu_EW)):
#    print('j='),
#    print(j)
    for i in range(2*LL):
#        a=0
#        print(i+susumu_NS[j])
        try:
            dp[j+1][i] = dp[j][i+susumu_EW[j]] | dp[j][i-susumu_EW[j]]
        except IndexError:
            if i < 0:
                dp[j+1][i] = dp[j][i+susumu_EW[j]]
            else:
                dp[j+1][i] = dp[j][i-susumu_EW[j]]

can_x = 0
if dp[len(susumu_EW)][x+LL] != 0:
    can_x = 1

#print(dp)

#print(can_x)
#print(can_y)

if can_x == 1 & can_y == 1:
    print('Yes')
else:
    print('No')








### FIXED CODE ###

import numpy as np

s=input()
x,y = [int(i) for i in input().split()]

#print(s)

susumu = [0]
for moji in s:
    if moji == 'F':
        susumu[-1] += 1
    else:
        susumu.append(0)

#print(susumu)

syokiti = susumu[0]

susumu_NS = [i for i in susumu[1::2] if i!=0]
susumu_EW = [i for i in susumu[2::2] if i!=0]

x -= syokiti

#print(susumu)
#print(susumu_NS)
#print(susumu_EW)
# ＥＷの部分和でx? NSの部分和でy？

LL = len(s)+2
dp = np.zeros(LL*2, dtype=bool)
dp[LL] = 1
for j in range(len(susumu_NS)):
    dpleft =np.r_[dp[susumu_NS[j]:],np.zeros(susumu_NS[j], dtype=bool)]
    dpright=np.r_[np.zeros(susumu_NS[j], dtype=bool),dp[:-susumu_NS[j]]]
    dp = dpleft|dpright
#    print(dp)

can_y = 0
if dp[y+LL] != False:
    can_y = 1
#print(dp)
#print(susumu_NS)

#########################################
LL = len(s)+2
dp = np.zeros(LL*2, dtype=bool)
dp[LL] = 1
for j in range(len(susumu_EW)):
    dpleft =np.r_[dp[susumu_EW[j]:],np.zeros(susumu_EW[j], dtype=bool)]
    dpright=np.r_[np.zeros(susumu_EW[j], dtype=bool),dp[:-susumu_EW[j]]]
    dp = dpleft|dpright
#    print(dp)

can_x = 0
if dp[x+LL] != False:
    can_x = 1

#print(dp)
#print(susumu_EW)

if can_x == 1 & can_y == 1:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N,M=map(int,input().split())
a=[0]*M
for i in range(M):
    a[i]=int(input())
MOD = 1000000007

dp=[0]*(N+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:dp[1]=1

for i in range(2,N+1):
    #n-1段目が安全なら
    if i-1 not in a:
        dp[i]+=dp[i-1]
    #n-2段目が安全なら
    if i-2 not in a:
        dp[i]+=dp[i-2]
    dp[i] = dp[i]%MOD
print(dp[N])

### FIXED CODE ###

N,M=map(int,input().split())
a=[0]*(N+1)
for i in range(M):
    a[int(input())]=1
MOD = 1000000007

dp=[0]*(N+1)
dp[0]=1
if a[1]==1:
    dp[1]=0
else:dp[1]=1

for i in range(2,N+1):
    #n-1段目が安全なら
    if a[i-1]==0:
        dp[i]+=dp[i-1]
    #n-2段目が安全なら
    if a[i-2]==0:
        dp[i]+=dp[i-2]
    dp[i] = dp[i]%MOD
print(dp[N])
### BUGGY CODE ###

prime = set([2])
for i in range(3, 100000000, 2):
    for j in prime:
        if i % j == 0:
            break
    else:
        prime.add(i)
n = int(input())
cnt = 0
for i in (int(input()) for _ in range(n)):
    if i in prime:
        cnt += 1
print(cnt)


### FIXED CODE ###

from sys import stdin
import math
def isPrime(x):
    if x == 2 or x == 3: return True
    elif (x < 2 or x % 2 == 0 or x % 3 == 0): return False
    s = int(math.sqrt(x) + 1)
    for i in range(5, s + 1, 2):
        if x % i == 0: return False
    return True
print(sum([isPrime(int(stdin.readline())) for _ in range(int(stdin.readline()))]))
### BUGGY CODE ###

import numpy as np
import sys
import time

def main():
    N = int(input())
    dp = np.array([[0]*3] * N)
    
    for i in range(N):
        w_all = list(map(int, input().split()))
        for j,  w in enumerate(w_all):
            if(i == 0):
                dp[i][j] = w
            else:
                tmp = dp[i-1]
                ind = np.ones(len(w_all), dtype=bool)
                ind[j] = False
                tmp = tmp[ind]
                dp[i][j] = max(tmp) + w
    print(int(max(dp[N-1])))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
 
 
def main():
    N = int(input())
    A, B, C = 0, 0, 0
    for _ in range(N):
        a, b, c = abc = map(int, input().split())
        A, B, C = max(B, C) + a, max(A, C) + b, max(A, B) + c
 
    print(max(A, B, C))
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys, math
from time import sleep
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from fractions import gcd
e = enumerate

sys.setrecursionlimit(10**7)
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [[float('inf')]*(H+1) for _ in range(N+1)]
#for i in range(H+1):
#    dp[0][i] = 0

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


for i, ab in e(AB):
    a, b = ab[0], ab[1]
    for j in range(H+1):

        if j==0:
            newval = b
        elif j%a==0:
            newval = j//a * b
        else:
            newval = (j//a+1) * b

        if j>=a:
            newval2 = dp[i][j-a] + b
        else:
            newval2 = float('inf')

        if j>=a:
            newval3 = dp[i+1][j-a] + b
        else:
            newval3 = float('inf')

        dp[i+1][j] = min(dp[i][j], newval, newval2, newval3)

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

print(dp[N][H])


### FIXED CODE ###

import sys, math
from time import sleep
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from fractions import gcd
e = enumerate

sys.setrecursionlimit(10**7)
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [[float('inf')]*(H+1) for _ in range(N+1)]


for i, ab in e(AB):
    a, b = ab[0], ab[1]
    for j in range(H+1):

        if j==0:
            newval = b
        elif j%a==0:
            newval = j//a * b
        else:
            newval = (j//a+1) * b

        if j>=a:
            newval2 = dp[i][j-a] + b
        else:
            newval2 = float('inf')

        if j>=a:
            newval3 = dp[i+1][j-a] + b
        else:
            newval3 = float('inf')

        dp[i+1][j] = min(dp[i][j], newval, newval2, newval3)


print(dp[N][H])
### BUGGY CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*m]
if all([1,i] not in l or [i,n] not in l for i in range(2,n)):print('IM',end='')
print('POSSIBLE')

### FIXED CODE ###

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
a=[]
b=[]
for _ in [0]*m:
    l=list(map(int,input().split()))
    if l[0]==1:a.append(l[1])
    if l[1]==n:b.append(l[0])
print('POSSIBLE' if set(a)&set(b) else 'IMPOSSIBLE')
### BUGGY CODE ###

N = int(input())
D = list(map(int,input().split()))
ans = 1
if D[0] != 0 or D.count(0) > 1:
  print(0)
  exit()

prev = 1
for i in range (N-2):
  count = D.count(i+1)
  ans = ( ans * (prev**count)  ) %998244353 
  prev = count
print(ans)
  

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
b = 1
ans = 1
dd=[0]*10**5
for i in d:
    dd[i]+=1
max = max(d)
if d[0] == 0 and d.count(0) == 1:
    for i in range(1, max+1):
        if dd[i] == 0:
            print(0)
            exit()
        if dd[i] == 1:
            ans *= b
        else:
            if b != 1:
                ans *= pow(b, dd[i], 998244353)
        b = dd[i]
    print(ans % 998244353)
else:
    print(0)
### BUGGY CODE ###

n = int(input())
adj = [list(map(int, input().split()))[2:] for _ in range(n)]

d = [-1] * n

s = 1
q = []
d[s - 1] = 0
q.append(s)
while len(q):
    u = q.pop()
    v = adj[u - 1]
    for vi in v:
        if d[vi - 1] == -1:
            d[vi - 1] = d[u - 1] + 1
    q += v


for i, di in enumerate(d):
    print(i + 1, di)

### FIXED CODE ###

n = int(input())
adj = [list(map(int, input().split()))[2:] for _ in range(n)]

d = [-1] * n

s = 1
q = []
d[s - 1] = 0
q.append(s)
while len(q):
    u = q.pop()
    v = adj[u - 1]
    for vi in v:
        if d[vi - 1] == -1:
            d[vi - 1] = d[u - 1] + 1         
            q.append(vi)
        elif d[vi - 1] > d[u - 1] + 1:
            d[vi - 1] = d[u - 1] + 1            
            q.append(vi)

for i, di in enumerate(d):
    print(i + 1, di)
### BUGGY CODE ###

import sys
#from fractions import Fraction

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def a(s):
	if s.count('.')==0:
		return int(s), 0
	else:
		p = s.index('.')
		if p == 1 and s[0]=='0':
			return int(s[2:]), len(s) - 2
		else:
			return int(s[:p]+s[p+1:]), len(s)-p-1


def main():
	n = int(input())
	#b , c = tin()
	al = [a(input()) for _ in range(n)]
	ret = 0
	for i, (vi, ki) in enumerate(al):
		for (vj, kj) in al[i+1:]:
			#pa((vi*vj)/(10**20))
			if (vi*vj) % (10**(ki+kj))==0:
				ret += 1
	return ret
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
#from fractions import Fraction
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def a(s):
	if s.count('.')==0:
		n2=0
		n5=0
		v = int(s)
	else:
		p = s.index('.')
		n2 = -(len(s) - p - 1)
		n5 = -(len(s) - p - 1)
		if p == 1 and s[0]=='0':
			v= int(s[2:])
		else:
			v = int(s[:p]+s[p+1:])
	while v % 2 == 0:
		v = v//2
		n2+=1
	while v % 5 == 0:
		v = v//5
		n5+=1
	return str(n2)+'_'+str(n5)

def main():
	n = int(input())
	#b , c = tin()
	al = [a(input()) for _ in range(n)]
	cal = collections.Counter(al)
	#pa(cal)
	ret = 0
	pp = set()
	for k in cal:
		for k2 in cal:
			if k+'_'+k2 in pp:
				continue
			#pa((vi*vj)/(10**20))
			if k==k2:
				a2, a5 = map(int, k.split('_'))
				if a2>=0 and a5 >= 0:
					ret += cal[k]*(cal[k]-1)//2
			else:
				a2, a5 = map(int, k.split('_'))
				b2, b5 = map(int, k2.split('_'))
				if a2+b2 >= 0 and a5+b5 >= 0:
					ret += cal[k]*cal[k2]
				
			pp.add(k+'_'+k2)
			pp.add(k2+'_'+k)
			#pa((k,k2,ret))
			
	return ret
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000)

N, K = map(int, raw_input().split())
H = map(int ,raw_input().split())
cost = [-1]*N

def sumOfCost(i):
  if cost[i] >= 0:
    return cost[i]
  elif i == 0:
    soc = 0
  else:
    soc = 1000000000
    for j in range(1, min(i+1,K+1)):
      if i-j < 0:
        break
      soc = min(soc, sumOfCost(i-j)+abs(H[i]-H[i-j]))
  cost[i] = soc
  return soc

print sumOfCost(N-1)
    



### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)

N, K = map(int, raw_input().split())
H = map(int ,raw_input().split())
cost = [-1]*N

def sumOfCost(i):
  if cost[i] >= 0:
    return cost[i]
  elif i == 0:
    soc = 0
  else:
    soc = 1000000000
    for j in reversed(range(1, min(i+1,K+1))):
      soc = min(soc, sumOfCost(i-j)+abs(H[i]-H[i-j]))
  cost[i] = soc
  return soc

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

s = input()
n = len(s)
point = 0
for i in range(n-1):
    for j in range(i+1,n):
        if int(s[i:j+1])%2019 == 0:
            point += 1
print(point)

### FIXED CODE ###

from sys import stdin
s = stdin.readline().rstrip()
n = len(s)
dic = {}
dic[0] = 1
now = 0
mul = 1
for i in range(n-1,-1,-1):
    now = (now+(10*mul)*int(s[i]))%2019
    if now in dic:
        dic[now] += 1
    else:
        dic[now] = 1
    mul *= 10
    mul %= 2019
print(sum(dic[i]*(dic[i]-1)//2 for i in dic))
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    A = [1] + list(map(int, input().split()))
    for i in range(2, N+1):
        A[i] *= A[i-1]
    for i in range(K+1, N+1):
        cur = A[i]//A[i-K]
        prev = A[i-1]//A[i-K-1]
        if cur > prev:
            print("Yes")
        else:
            print("No")


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = [1] + list(map(int, input().split()))
    for i in range(K+1, N+1):
        if A[i] > A[i-K]:
            print("Yes")
        else:
            print("No")


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

def main():
    from heapq import heappop as hpop
    from heapq import heappush as hpush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    visit = [False]*n
    h = []
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i = -i
        jj = (j+1) % n
        if visit[j]:
            if a[j] != b[j]:
                print(-1)
                return 0
            visit[j-1] = True
            visit[jj] = True
            continue
        temp = i-a[j]
        temp2 = b[j-1]+b[jj]
        sho = temp//temp2
        if sho == 0:
            if a[j] != b[j]:
                print(-1)
                return 0
            visit[j-1] = True
            visit[jj] = True
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    print(cnt)


main()

### FIXED CODE ###

def main():
    from heapq import heappop as hpop
    from heapq import heappush as hpush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i = -i
        jj = (j+1) % n
        temp = i-a[j]
        temp2 = b[j-1]+b[jj]
        sho = temp//temp2
        if sho == 0:
            if temp:
                print(-1)
                return 0
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    print(cnt)
main()
### BUGGY CODE ###

S=list(input())
count = 0
i = 0
while i+1<len(S):
  if S[i] == 'B' and S[i+1] == 'W':
    S[i],S[i+1]='W','B'
    i = 0
    count += 1
  else:
    i+=1
print(count)

### FIXED CODE ###

S=input()
S_list=list(S)
num_B = S.count('W')
count = 0
i = 0
for nb in range(num_B):
  while S_list[i] != 'W': i+=1
  count += i - nb
  S_list[nb],S_list[i]=S_list[i],S_list[nb]
  i+=1
print(count)
### BUGGY CODE ###

import math
def main():
    ans = 0
    k = int(input())
    for i in range(k):
        for j in range(k):
            for l in range(k):
                ans += math.gcd(i+1,math.gcd(j+1,l+1))
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import gcd
def main():
    ans = 0
    k = int(input())
    for i in range(k):
        for j in range(k):
            for l in range(k):
                ans += gcd(i+1,gcd(j+1,l+1))
    print(ans)


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

import copy
N = int(input())
X = list(map(int, input().split()))

for i in range(N):
    tmp = copy.deepcopy(X)
    tmp.pop(i)
    tmp.sort()
    print(tmp[(len(tmp)+1)//2-1])


### FIXED CODE ###

import copy
N = int(input())
X = list(map(int, input().split()))
tmp = copy.deepcopy(X)
tmp.sort()

a = tmp[int(len(tmp)/2)-1]
b = tmp[int(len(tmp)/2)]

for i in X:
    print(b if i<(a+b)/2 else a)
### BUGGY CODE ###

#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
#n=int(input())
#import fractions
#import math
#lis=list(input().split())
#lis=list(map(float,input().split()))
#n=int(input())
#S=input()

import itertools

lis=list(map(int,input().split()))
alist=[-1]
ans=1
for i in range(lis[1]):
    alist.append(int(input()))
alist.append(lis[0]+1)

for i in range(lis[1]+1):
    l=alist[i+1]-alist[i]-2
    tmp=0
    t=int((l+l%2)/2)
    h=int((l-l%2)/2)
    for j in range(h+1):
        tmp+=len(list(itertools.combinations(range(t+j),h-j)))%((10**9)+7)
    ans=(ans*tmp)%((10**9)+7)
print(ans)


### FIXED CODE ###

lis=list(map(int,input().split()))
alist=[0]*(lis[0]+1)
for i in range(lis[1]):
    a=int(input())
    alist[a]=1
steps=[0]*(lis[0]+2)
steps[1]=1
mod=(10**9)+7
for i in range(2,lis[0]+2):
    if alist[i-1]==0:
        steps[i]=(steps[i-1]+steps[i-2])%mod
ans=steps[-1]
print(ans)
### BUGGY CODE ###

N = int(input())
dic = []
count = []
ans = 0

for i in range(N):
  check = 0
  S = "".join(sorted(input()))
  for j in range(len(dic)):
    if dic[j] == S:
      ans += count[j]
      check = 1
      count[j] += 1
      break
    
  if check == 0:
    dic.append(S)
    count.append(1)


print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

N = int(input())
dic = []
ans = 0

for i in range(N):
  S = "".join(sorted(input()))
  dic.append(S)

dic.sort()

for i in range(N):
  S = dic[i]
  r = bisect_right(dic, S)
  ans += r-i-1


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

n = int(raw_input())
ais = [int(raw_input()) for _ in range(n)]
tails = []
import bisect
for a in ais:
	if not(tails) or not(tails[0] < a):
		tails = [a] + tails 
	else:
		m = -1
		for ii in range(len(tails)):
			if tails[ii] < a: m = max(ii, m)
		if m != -1:
			tails[m] = a

print len(tails)

### FIXED CODE ###

n = int(raw_input())
ais = [int(raw_input()) for _ in range(n)]
tails = []
import bisect
for a in ais:
	if not(tails) or (tails[-1] >= a):
		tails.append(a)
	else:
		# maintain a decreaing tails
		986643321
		lo,hi = 0, len(tails) - 1
		while(lo<hi):
			med= (lo + hi)/2
			if tails[med] < a:
				hi = med
			else:
				lo = med + 1
		tails[lo] = a
print len(tails)
### BUGGY CODE ###

from bisect import bisect_left
 
N = int(input())
L = [int(i) for i in input().split()]
L.sort()
 
cnt = 0
for i in range(0,N):
  for j in range(i+1,N):
    t = L[i]+L[j]
    idx = bisect_left(L,t,lo=j+1)
    cnt += max(0,idx-j-1)
print(cnt)

### FIXED CODE ###

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

from bisect import bisect_left 
cnt = 0
for i in range(0,N):
  for j in range(i+1,N):
    t = L[i]+L[j]
    idx = bisect_left(L,t)
    cnt += max(0,idx-j-1)
print(cnt)
### BUGGY CODE ###

def main():
    s=input()
    q=int(input())
    queryy=[]

    for i in range(q):
        queryy.append(list(input().split()))
    for query in queryy:
    #   print(query)
        if query[0]=="1":
            s=s[::-1]
        else:
            if query[1]=="1":
                s=str(query[2])+s
            else:
                s+=str(query[2])
    print(s)

if __name__=="__main__":
    main()          



### FIXED CODE ###

def main():
    s=input()
    q=int(input())
    queryy=[]
    sent="a"
    back="a"
    for i in range(q):
        queryy.append(tuple(input().split()))
    check=-1
    for query in queryy:
    #   print(query)
        if query[0]=="1":
            check*=-1
        else:
            if query[1]=="1":
                if check==-1:
                    sent+=str(query[2])
                   # s=str(query[2])+s
                else:
                    back+=str(query[2])
                   # s+=str(query[2])
                    
            else:
                if check==-1:
                    back+=str(query[2])
                    #s+=str(query[2])
                else:
                    sent+=str(query[2])
                    #s=str(query[2])+s
   # print(type(sent))
    #if sent[0]=="1":
     #   sent=sent[1:]
    sent=sent[1:]
    sent=sent[::-1]   
    back=back[1:]

    if check==1:
        s=sent+s+back        
        print(s[::-1]) 
    else:
        s=sent+s+back
        print(s)

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

N, M = map(int, input().split())
Dp = [10**10]*(2**N)
Dp[0] = 0

for i in range(M): #カギiで
    a,_=map(int, input().split())
    c = list(map(int, input().split()))
    d = sum((1<<p-1) for p in c) #iで開けられる宝箱の2bit表記
    for j in range(2**N):
        ope = j|d
        Dp[ope] = min(Dp[ope], Dp[j] + a)

if Dp[-1] == 10**10:
    print(-1)
else:
    print(Dp[-1])



### FIXED CODE ###

N, M = map(int, input().split())
Inf = 10**8
Dp = [Inf]*(2**N)
Dp[0] = 0

for i in range(M): #カギiで
    a,_=map(int, input().split())
    c = list(map(int, input().split()))
    d = sum((1<<p-1) for p in c) #iで開けられる宝箱の2bit表記
    for j in range(2**N):
        ope = j|d
        Dp[ope] = min(Dp[ope], Dp[j] + a)

if Dp[-1] == Inf:
    print(-1)
else:
    print(Dp[-1])
### BUGGY CODE ###

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

### FIXED CODE ###

import bisect
 
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        tmp=a[i]+a[j]
        index=bisect.bisect_left(a,tmp)
        ans+=index-j-1
print(ans)