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

#!/usr/bin/env python3

#import
import math
#import numpy as np
N = int(input())
L = list(map(int, input().split()))

L.sort()

def is_ok(arg, cmin, cmax):
    return L[arg] > cmin and L[arg] < cmax

def meguru_bisect(ok, ng, cmin, cmax):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid, cmin, cmax):
            ok = mid
        else:
            ng = mid
    return ok

ans = 0

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        a = L[i]
        b = L[j]
        cmin = b - a
        cmax = a + b
        t = meguru_bisect(j, N, cmin, cmax)
        ans += t - j

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

#import
import math
#import numpy as np
N = int(input())
L = list(map(int, input().split()))

L.sort()

def is_ok(arg, cmin, cmax):
    return L[arg] > cmin and L[arg] < cmax

def meguru_bisect(ok, ng, cmin, cmax):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid, cmin, cmax):
            ok = mid
        else:
            ng = mid
    return ok

ans = 0

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        a = L[i]
        b = L[j]
        cmin = b - a
        cmax = a + b
        t = meguru_bisect(j, N, cmin, cmax)
        ans += t - j

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

from collections import defaultdict
N,M = list(map(int,input().split()))
A = []
B = []
Dot = []
price_howmany = defaultdict(int)
for _ in range(N):
    tmp = list(map(int,input().split()))
    price_howmany[tmp[0]] += tmp[1]
    # A.append(tmp[0])
    # B.append(tmp[1])
    # Dot.append(tmp[0]*tmp[1])

price_howmany = dict(price_howmany)

def solve():
    price = 0
    many = 0
    global price_howmany
    global M
    while M > 0:
        low_price = min(price_howmany.keys())
        many = min(M,price_howmany[low_price])
        price += many * low_price
        M -= many
        price_howmany.pop(low_price)
    print(price)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

# from collections import defaultdict
# N,M = list(map(int,input().split()))
# price_howmany = defaultdict(int)
import sys

stdin = sys.stdin

read_int = lambda : list(map(int,stdin.readline().split()))

N,M = read_int()
price_howmany = {}
# price_list = []

price_set = set()
for _ in range(N):
    tmp = read_int()
    # if tmp[0] not in price_set:
        # price_list.append(tmp[0])
    price_set.add(tmp[0])
    if tmp[0] in price_howmany:
        price_howmany[tmp[0]] += tmp[1]
    else:
        price_howmany[tmp[0]] = tmp[1]
# price_list.sort(reverse=True)
price_list = sorted(list(price_set))

# price_howmany = dict(price_howmany)

def solve():
    price = 0
    global M
    # while M > 0:
        # low_price = min(price_howmany.keys())
        # low_price = price_list.pop()
        # many = min(M,price_howmany.pop(low_price))
        # price += many * low_price
        # M -= many
    for low_price in price_list:
        many = min(M,price_howmany.pop(low_price))
        price += many * low_price
        M -= many
        if M == 0: break
    print(price)

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

def main():
    N = int(input())
    S = input()
    ok, ng = 0, N + 1
    while abs(ok - ng) > 1:
        x = (ok + ng) // 2
        for i in range(N - x + 1):
            if S.find(S[i: i + x], i + x) > 0:
                ok = x
                break
        else:
            ng = x
 
    print(ok)
 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    ok, ng = 0, N + 1
    while abs(ok - ng) > 1:
        x = (ok + ng) // 2
        check = set()
        for i in range(N - x + 1):
            check.add(S[i: i + x])
            if S[i + x: i + 2 * x] in check:
                ok = x
                break
        else:
            ng = x

    print(ok)


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

#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
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()))

def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n]*pow(fact[r],mod-2,mod)*pow(fact[n-r],mod-2,mod) % mod
n = I()
a = LI()
c = list(Counter(a).items())
c.sort(key = itemgetter(1),reverse = True)
x = c[0][0]
fact = [0]*(n+2)
fact[0] = 1
for i in range(1,n+2):
    fact[i] = i*fact[i-1]

lst = []
for i in range(n+1):
    if a[i] == x:
        lst.append(i+1)
a,b = lst[0],lst[1]
for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)
    

### FIXED CODE ###

#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
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()))
def f(a, b):
    if b == 0: 
        return 1
    if b % 2 == 0:
        d = f(a, b // 2)
        return d * d % mod
    if b % 2 == 1:
        return (a * f(a, b - 1)) % mod


def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n] * invfact[r] * invfact[n-r] % mod

n = I()
a = LI()
cnt = [0]*(n+1)
for i in range(n+1):
    if cnt[a[i]]:
        a = cnt[a[i]]
        b = i+1
        break
    else:
        cnt[a[i]] = i+1

fact = [1]*(n+2)
invfact = [1]*(n+2)
for i in range(1,n+2):
    fact[i] = i*fact[i-1] % mod
    invfact[i] = invfact[i-1] * f(i,mod-2) % mod

for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)
### BUGGY CODE ###

# 15:20
n = int(input())
s = []
for i in range(n):
    s.append(sorted(input()))
ans = 0
for i in range(n-1):
    ans += s[i+1:].count(s[i])
print(ans)


### FIXED CODE ###

# 15:20 -16:08 giveup
# 21:45 -22:33 review
from collections import Counter

# 3
# acornistnt
# peanutbomb
# constraint
n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
# s is ['acinnorstt', 'abbemnoptu', 'acinnorstt']
counter = Counter(s)
# counter is Counter({'acinnorstt': 2, 'abbemnoptu': 1})
# counter.values() is dict_values([3, 2])
ans = sum(x*(x-1)//2 for x in counter.values())
print(ans)
### BUGGY CODE ###

N=int(input())
B=[]


for i in range(N):
    a,b, = map(int, input().split())
    B.append([a,b])

a=B[0][0]
b=B[0][1]

for i in range(1,N):
    a1=B[i][0]
    b1=B[i][1]
    if a>B[i][0] or b>B[i][1]:
        while a>a1 or b>b1:
            a1+=B[i][0]
            b1+=B[i][1]
        a=a1
        b=b1
    else:
        a=B[i][0]
        b=B[i][1]
print(a+b)


### FIXED CODE ###

N = int(input())

A = 1
B = 1
for _ in range(N):
    x, y = map(int, input().split())
    na = A // x if A % x == 0 else A // x + 1
    nb = B // y if B % y == 0 else B // y + 1
    n = max(na, nb)
    A = n * x
    B = n * y

print(A + B)
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

H,W = map(int,input().split())
S = [[] for i in range(H)]
for i in range(H):
    S[i] = list(str(input()))

lights = [[(0,0) for j in range(W)] for i in range(H)]


def count_ver(i,j):
    cnt = 0
    for x in range(i,W):
        if S[j][x] == ".":
            cnt += 1
        else:
            break
    for x in range(i,W):
        if S[j][x] == ".":
            ver,hor = lights[j][x]
            lights[j][x] = (cnt,hor)
        else:
            break
    return cnt


def count_hor(i,j):
    cnt = 0
    for y in range(j,H):
        if S[y][i] == ".":
            cnt += 1
        else:
            break
    for y in range(j,H):
        if S[y][i] == ".":
            ver,hor = lights[y][i]
            lights[y][i] = (ver,cnt)
        else:
            break
    return cnt

ans = -1
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ver,hor = lights[i][j]
            if ver == 0:
                ver = count_ver(j,i)
                # print("ver",ver)
            if hor == 0:
                hor = count_hor(j,i)
                # print("hor",hor)
            ans = max(ans,hor+ver-1)
        # print("y,x:",i,j)
        # print("ver,hor",ver,hor)

# print(lights)
print(ans)


### FIXED CODE ###

import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

H,W = map(int,input().split())
S = [[] for i in range(H)]
for i in range(H):
    S[i] = list(str(input()))

lights = [[(0,0) for j in range(W)] for i in range(H)]

def count_ver(i,j):
    cnt = 0
    for x in range(i,W):
        if S[j][x] == ".":
            cnt += 1
        else:
            break
    for x in range(i,i+cnt):
        ver,hor = lights[j][x]
        lights[j][x] = (cnt,hor)
    return cnt


def count_hor(i,j):
    cnt = 0
    for y in range(j,H):
        if S[y][i] == ".":
            cnt += 1
        else:
            break
    for y in range(j,j+cnt):
        ver,hor = lights[y][i]
        lights[y][i] = (ver,cnt)
    return cnt

ans = -1
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ver,hor = lights[i][j]
            if ver == 0:
                ver = count_ver(j,i)
            if hor == 0:
                hor = count_hor(j,i)
            ans = max(ans,hor+ver-1)

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

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N,K=LI()
#AB=[LI() for i in range(N)]

counts={}
l=[]
for i in range(N):
	ab=LI()

	if not counts.get(ab[0]):
		counts[ab[0]]=ab[1]
	else:
		counts[ab[0]]+=ab[1]
	if ab[0] not in l:
		l.append(ab[0])

l.sort()
c=0
for item in l:
	c+=counts.get(item)
	if c>=K:
		print(item)
		exit()


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N,K=LI()
A=[]
B=[]
AB=[]
for i in range(N):
	a,b=LI()
	A.append(a)
	B.append(b)
	AB.append([a,b])
A=list(set(A))
A.sort()
counts={}
for a in A:
	counts[a]=0

for ab in AB:
	counts[ab[0]]+=ab[1]
if K<N/2:
	c=0
	for item in A:
		c+=counts.get(item)
		if c>=K:
			print(item)
			exit()
else:
	c=sum(B)
	for item in reversed(A):
		c-=counts.get(item)
		if c<K:
			print(item)
			exit()
### BUGGY CODE ###

import numpy as np
N=int(input())
L=np.array(list(map(int, input().split())))
S=0
L.sort()
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]: 
                S+=1
            else:
                break
print(S)

### FIXED CODE ###

import bisect

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

for i in range(N):
    for j in range(i+1,N):
        S+=bisect.bisect_left(L,L[i]+L[j])-j-1
print(S)
### BUGGY CODE ###

import numpy as np

def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j >= a[i]:
                dp[j] = min(dp[j], dp[j-a[i]] + b[i])
    return min(dp[H:Hmax+1])


H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = [INF for _ in range(Hmax+1)] 
dp[0] = 0
print(rec_z())

### FIXED CODE ###

def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j >= a[i]:
                dp[j] = min(dp[j], dp[j-a[i]] + b[i])
    return min(dp[H:Hmax+1])
 
 
H, N = map(int,input().split())
a = []
b = []
for i in range(N):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = [INF for _ in range(Hmax+1)] 
dp[0] = 0
print(rec_z())
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = IR(n)
LIS = [A[0]]
for i in range(1, n):
    if A[i] <= LIS[0]:
        LIS = [A[i]] + LIS
    else:
        LIS[bisect_left(LIS, A[i]) - 1] = A[i]


print(len(LIS))





### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = IR(n)
IS = deque([L[0]])
for i in range(1, n):
    if L[i] <= IS[0]:
        IS.appendleft(L[i])
    else:
        IS[bisect_left(IS, L[i]) - 1] = L[i]



print(len(IS))
### BUGGY CODE ###

import math

K = int (input())
sum = 0

for i in range (1, K+1):
    for j in range (1, K+1):
        for k in range (1, K+1):
            sum += math.gcd(i, math.gcd(j,k))

print (sum)

### FIXED CODE ###

import math

t = int (input())
sum = 0

for i in range (1, t+1):
    for j in range (1, t+1):
        aux = math.gcd(i,j)
        for k in range (1, t+1):
            sum += math.gcd(aux, k)

print (sum)
### BUGGY CODE ###

s = input()
k = int(input())

sl = [s]
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        ss = s[i:j]
        sl.append(ss)
sl = sorted(list(set(sl)))
print(sl[k-1])

### FIXED CODE ###

s = input()
k = int(input())

sl = [s]
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        if j - i > k:
            break
        ss = s[i:j]
        sl.append(ss)
sl = sorted(list(set(sl)))
print(sl[k-1])
### BUGGY CODE ###

H, W = map(int, input().split())
sy, sx = map(lambda x: int(x) - 1, input().split())
gy, gx = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]
seen = [[-1] * W for _ in range(H)] 
from collections import deque

def bfs(maze, seen, sy, sx, gy, gx):
    queue = deque()
    queue.append([sy, sx, 0])
    while queue:
        y, x, c = queue.popleft()
        if seen[y][x] > -1:
            continue
        seen[y][x] = c
        if seen[gy][gx] > -1:
            return c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if (i == -1 and j == 0) or (i == 1 and j == 0) or (i == 0 and j == -1) or (i == 0 and j == 1):   
                    dy = y + i
                    dx = x + j
                    if dy < 0 or H <= dy or dx < 0 or W <= dx or seen[dy][dx] > -1:
                        continue
                    if maze[dy][dx] == '#':
                        continue
                    queue.appendleft([dy, dx, c])
                dy = y + i
                dx = x + j
                if dy < 0 or H <= dy or dx < 0 or W <= dx or seen[dy][dx] > -1:
                    continue
                if maze[dy][dx] == '#':
                    continue
                queue.append([dy, dx, seen[y][x] + 1])
    return -1

print(bfs(maze, seen, sy, sx, gy, gx))


### FIXED CODE ###

H, W = map(int, input().split())
sy, sx = map(lambda x: int(x) - 1, input().split())
gy, gx = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]
seen = [[-1] * W for _ in range(H)] 
from collections import deque

def bfs(maze, seen, sy, sx, gy, gx):
    queue = deque()
    queue.append([sy, sx, 0])
    while queue:
        y, x, c = queue.popleft()
        if seen[y][x] > -1:
            continue
        seen[y][x] = c
        if seen[gy][gx] > -1:
            return c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if (i == -1 and j == 0) or (i == 1 and j == 0) or (i == 0 and j == -1) or (i == 0 and j == 1):   
                    dy = y + i
                    dx = x + j
                    if dy < 0 or H <= dy or dx < 0 or W <= dx or seen[dy][dx] > -1:
                        continue
                    if maze[dy][dx] == '#':
                        continue
                    queue.appendleft([dy, dx, c])
                dy = y + i
                dx = x + j
                if dy < 0 or H <= dy or dx < 0 or W <= dx or seen[dy][dx] > -1:
                    continue
                if maze[dy][dx] == '#':
                    continue
                queue.append([dy, dx, seen[y][x] + 1])
    return -1

print(bfs(maze, seen, sy, sx, gy, gx))
### BUGGY CODE ###

from collections import deque
n,q=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
px=[list(map(int,input().split())) for _ in range(q)]

adlist=[]
finish=set()
def dfs():
    while deq:
        now=deq.pop()
       # print(now)
        finish.add(now)
        for i in range(len(adlist[now-1])):
            #print(adlist[now-1][i],now)
            if adlist[now-1][i] not in finish:
                point[adlist[now-1][i]-1]+=point[now-1]
                deq.append(adlist[now-1][i])
point=[0]*n
for h in range(n):    
    adlist.append([])
for j in range(n-1):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
for i in range(q):
    point[px[i][0]-1]+=px[i][1]
#print(point)
deq=deque()
deq.append(1)
#print(deq)
dfs()
for i in range(n):
    print(point[i],end=" ")

"""
finish=set()
finish.add(1)
#print(adlist)
dfs(1,finish)#引数がけすノード
print(ans)"""

### FIXED CODE ###

from collections import deque
n,q=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
px=[list(map(int,input().split())) for _ in range(q)]

adlist=[]
finish=set()

point=[0]*n
for h in range(n):    
    adlist.append([])
for j in range(n-1):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
for i in range(q):
    point[px[i][0]-1]+=px[i][1]
#print(point)
deq=deque()
deq.append(1)


while deq:
    now=deq.pop()
       # print(now)
    finish.add(now)
    for i in range(len(adlist[now-1])):
        #print(adlist[now-1][i],now)
        if adlist[now-1][i] not in finish:
            point[adlist[now-1][i]-1]+=point[now-1]
            deq.append(adlist[now-1][i])

for i in range(n):
    print(point[i],end=" ")
### BUGGY CODE ###

H,N,*T = map(int,open(0).read().split())

#dpテーブルの設定と初期化
dp = [0] + [10 ** 9] * H

#各魔法について
for d,c in zip(*[iter(T)] * 2):
  #d,cはそれぞれ魔法ダメージと魔法のコスト
  #dpテーブルの各HPについて
  for j in range(H + 1):
    k = max(j - d,0)
    #ダメージjを与える時のコストについて、
    #魔法iを新たに使った場合と、既存の最小コストを比較し更新する
    l = dp[k] + c
    dp[j] = min(l,dp[j])

print(dp[-1])

### FIXED CODE ###

def main():
    h,n,*t=map(int,open(0).read().split())
    d=[0]+[10**18]*h
    for a,b in zip(*[iter(t)]*2):
        for j in range(h+1):
            k=j-a
            if k<0:k=0
            c=d[k]+b
            if c<d[j]:d[j]=c
    print(d[h])
main()
### BUGGY CODE ###

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

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if j - i == k - j:
                continue
            elif s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                ans += 1
print(ans)

### FIXED CODE ###

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

r = g = b = 0
for i in range(n):
    if s[i] == 'R':
        r += 1
    elif s[i] == 'G':
        g += 1
    else:
        b += 1

x = 0
for i in range(n):
    for j in range(i+1, n):
        k = j + j - i
        if k < n and s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            x += 1
print(r*g*b-x)
### BUGGY CODE ###

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

_p = [(x+1)/2 for x in p]

ans = 0
for i in range(n-k+1):
    _ans = sum(_p[i:i+k])
    if _ans > ans:
        ans = _ans
print(ans)


### FIXED CODE ###

def calc(x):
    return (x+1)/2

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

_ans = sum(p[0:k])
ans = _ans
for x in range(n-k):
    # print(x, x + k)
    _ans = _ans - p[x] + p[x + k]
    ans = max(ans, _ans)

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

from math import ceil


def solve(string):
    a, b = map(int, string.split())
    ans = ceil(a / 0.08)
    while ans // 10 != b:
        ans += 1
    return str(ans) if ans * 2 // 25 == a else "-1"


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


### FIXED CODE ###

from math import ceil


def solve(string):
    a, b = map(int, string.split())
    ans = ceil(a / 0.08)
    while ans // 10 < b:
        ans += 1
    return str(ans) if ans * 2 // 25 == a and ans // 10 == b else "-1"


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1 ,N):
            a = L[i]
            b = L[j]
            c = L[k]
            if a < b + c and b < a + c and c < a + b:
                ans += 1
            else:
                break
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
l = list(map(int,input().split()))
l.sort()
#print(l)


ans = 0
for i in range(N - 1 , 1, -1):
    for j in range(i - 1 , 0 , -1):
        #work = l[:j]
        x = l[i] - l[j]
        #idx = bisect.bisect_right(work, x)
        idx = bisect.bisect_right(l, x)
        ans += max(j - idx , 0)
print(ans)