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

# https://atcoder.jp/contests/abc128/submissions/8312583
# 写経

def solve():
    from heapq import heappush, heappop
    from collections import defaultdict
    from operator import itemgetter
    import sys

    input = sys.stdin.readline

    inf = 1 << 31

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

    e = []  # 通行止めと解除にクエリ分割
    for _ in range(n):
        s, t, x = map(int, input().split())
        # 区間[s, t)に通行止め
        e.append((t - x, 0, x))  # 通行止め解除/0にすることで、解除と開始が同時刻の場合、先に解除される
        e.append((s - x, 1, x))  # 通行止め開始/1にすることで、同上

    for i in range(q):
        d = int(input())
        e.append((d, 2, i))  # 求値クエリ/2にすることで、通行止めの設定解除の反映後に到着する

    e.sort(key=itemgetter(0, 1))

    cnt = defaultdict(int)
    cnt[inf] = 1
    h = [inf]

    ret = [-1] * q
    for time, type, x in e:
        if type == 0:
            cnt[x] -= 1
        elif type == 1:
            heappush(h, x)
            cnt[x] += 1
        else:
            while not (cnt[h[0]]):
                heappop(h)
            curr = h[0]
            if curr != inf:
                ret[x] = curr

    print(*ret, sep='\n')


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = [" "] + lc()
q = ni()
k = list(li())

def find_ans(k:int):
    cnt = [0,0,0]
    ans = 0
    
    for i in range(1, n+1):
        
        if s[i] == 'C':
            ans += cnt[2]

        if i-k+1 > 0:
            if s[i-k+1] == 'D':
                cnt[0] -= 1
                cnt[2] -= cnt[1]
                
            elif s[i-k+1] == 'M':
                cnt[1] -= 1
                
        if s[i] == 'D':
            cnt[0] += 1    
        
        elif s[i] == 'M':
            cnt[2] += cnt[0]
            cnt[1] += 1

            
    return ans
        
for ki in k:
    print(find_ans(ki))

### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = " " + ns()
q = ni()
k = list(li())

def find_ans(k:int):
    cnt = [0,0,0]
    ans = 0
    
    for i in range(1, n+1):
        
        if s[i] == 'C':
            ans += cnt[2]

        if i-k+1 > 0:
            if s[i-k+1] == 'D':
                cnt[0] -= 1
                cnt[2] -= cnt[1]
                
            elif s[i-k+1] == 'M':
                cnt[1] -= 1
                
        if s[i] == 'D':
            cnt[0] += 1    
        
        elif s[i] == 'M':
            cnt[2] += cnt[0]
            cnt[1] += 1

            
    return ans
        
for ki in k:
    print(find_ans(ki))
### BUGGY CODE ###

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

pair = n*(n - 1)/2
not_4 = 0
ans = 'Yes'
for i in range(len(a)):
  for j in range(len(a)):
    
    if i == j:
      continue
      
    if a[i]*a[j]%4 != 0:
      not_4 += 1
      
    if not_4 >= pair:
      ans = 'No'
      break
    
print(ans)

  

### FIXED CODE ###

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

four = 0
two = 0
one = 0
for i in a:
  if i%4 == 0:
    four += 1
  elif i%2 == 0 and i%4 != 0:
    two += 1
  elif i%2 != 0:
    one += 1

if four >= one or four + 1 >= two//2 + two%2 + one or n == two:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

def resolve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(m):
        ma = max(a)
        a[a.index(ma)] //= 2
    print(sum(a))


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

import heapq


def resolve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    query = []
    for i in range(n):
        heapq.heappush(query, -a[i])
    for i in range(m):
        nexta = -1 * heapq.heappop(query) // 2
        heapq.heappush(query, -nexta)
    print(-sum(query))


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

from numba import njit

R, C, K = map(int, input().split())
rcvs = [tuple(map(int, input().split())) for _ in range(K)]

rcvs.sort(key = lambda t: t[1] * 30000 + t[0])

@njit(cache = True)
def solve(rcvs):
    dp = [[0] * (R+1) for _ in range(4)]
    index = 0
    for c in range(C+1):
        while index < K and rcvs[index][1] == c:
            x, _, v = rcvs[index]
            if dp[3][x] < dp[2][x] + v:
                dp[3][x] = dp[2][x] + v
            if dp[2][x] < dp[1][x] + v:
                dp[2][x] = dp[1][x] + v
            if dp[1][x] < dp[0][x] + v:
                dp[1][x] = dp[0][x] + v
            index += 1
            for r in range(x, R):
                if dp[0][r+1] < max(dp[0][r], dp[1][r], dp[2][r], dp[3][r]):
                    dp[0][r+1] = max(dp[0][r], dp[1][r], dp[2][r], dp[3][r])
                else:
                    break
            #print(dp)   
        
    ans = max([max(row) for row in dp])
    return ans

print(solve(rcvs))

### FIXED CODE ###

R, C, K = map(int, input().split())
points_dict = dict()
for _ in range(K):
    r, c, v = map(int, input().split())
    points_dict[r * 30000 + c] = v

dp = [[[0] * (C+1) for _ in range(R+1)] for _ in range(4)] # dp[4][R+1][C+1]
index = 0
for i in range(1, R+1):
    for j in range(1, C+1):
        #移動
        for k in range(4):
            if dp[0][i][j] < dp[k][i-1][j]:
                dp[0][i][j] = dp[k][i-1][j]
            if dp[k][i][j] < dp[k][i][j-1]:
                dp[k][i][j] = dp[k][i][j-1]
        #あれば、拾うかどうか
        if i * 30000 + j in points_dict:
            v = points_dict[i * 30000 + j]
            for k in range(3, 0, -1):
                if dp[k][i][j] < dp[k-1][i][j] + v:
                    dp[k][i][j] = dp[k-1][i][j] + v
"""
for i in range(4):
    print(i)
    print(*dp[i], sep = '\n')
"""
print(max((dp[i][R][C] for i in range(4))))
### BUGGY CODE ###

s,c = map(int,input().split())

ans = 0
while s>=1 and c>=2:
    s -= 1
    c -= 2
    ans += 1 

print(ans + c//4)

### FIXED CODE ###

s,c = map(int,input().split())

ans = min(s,c//2)
c -= ans*2
print(ans + c//4)
### BUGGY CODE ###

from math import log2,floor
N = int(input())
A = list(map(int,input().split()))
L = max([len(bin(x)) for x in A])
mod = 10**9+7
ans = 0
for i in range(L):
    bits = 0
    for x in A:
        if (x>>i)&1:
            bits += 1
    ans = (ans+(bits*(N-bits)%mod)*((2**i)%mod))%mod
print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
mod = 10**9 + 7
 
def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))
 
def main():
    n = ni()
    a = na()
    ans = 0
    for i in range(61):
        cnt = 0
        for ai in a:
            if (ai >> i) & 1:
                cnt += 1
        ans += ((cnt * (n - cnt)) * 2**i) % mod
    ans %= mod
    print(ans)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

Al = sorted(A,reverse=True)[:K]
Bl = sorted(B,reverse=True)[:K]
Cl = sorted(C,reverse=True)[:K]

ABl = []
for a in Al:
    for b in Bl:
        ABl.append(a+b)

result = []
ABl = sorted(ABl,reverse=True)[:K]
for ab in ABl:
    for c in Cl:
        result.append(ab+c)

result.sort(reverse=True)

for i in range(K):
    print(result[i])


### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
e=[]
for ai in a:
    for bi in b:
        e.append(ai+bi)
e.sort(reverse=True)
e=e[:k]
ans=[]
for ci in c:
    for ei in e:
        ans.append(ci+ei)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

from itertools import combinations
def solve():
    n = int(input())
    a = list(map(int, input().split()))

    m = len(a)
    cnt = 0
    for i in combinations(range(m), 2):
        x = i[0]
        y = i[1]
        if abs(x-y) == a[x]+ a[y]:
            cnt += 1



    
    return cnt




print(solve())


### FIXED CODE ###

from collections import*
def solve():
    n = int(input())
    a = list(map(int, input().split()))

    l = []
    r = []
    for i, j in enumerate(a):
        l += [i + j]
        r += [i - j]

    cnt = 0
    l = Counter(l)
    for r in r:
        cnt += l.get(r, 0)

    
    return cnt




print(solve())
### BUGGY CODE ###

from fractions import gcd

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

ans = 0
g = gcd(a,b)
while g > 1:
    for i in range(2,g+1):
        if g%i == 0:
            ans+=1
            while g%i == 0:
                g //= i
            break
print(ans+1)

### FIXED CODE ###

from fractions import gcd
from math import sqrt, ceil

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

ans = 0
tmp = 1
g = gcd(a,b)
while g > 1:
    for i in range(tmp+1,ceil(sqrt(g))):
        if g%i == 0:
            ans += 1
            tmp = i
            while g%i == 0:
                g //= i
            break
    else:
        # もうgでしか割れないはず
        ans += 1
        break
print(ans+1)
### BUGGY CODE ###

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

B=[]
for i in range(1,N+1):
    B.append(A.index(i)+1)

print(' '.join(map(str, B)))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
d=[0]*N
for i in range(N):
    d[A[i]-1]=i+1

print(' '.join(map(str, d)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

s = input().split() 
s = list(s[0])
t = input().split() 
t = list(t[0])
f = [[] for _ in range(26)]

for i in range(len(s)):
    f[ord(s[i])-97].append(i)
g = [-1 for _ in range(len(t))]
if len(f[ord(t[0])-97]) == 0:
    print(-1)
    sys.exit()
g[0] = f[ord(t[0])-97][0]
cnt = 0
for i in range(1,len(t)):
    for j in f[ord(t[i])-97]:
        if j > g[i-1]:
            g[i] = j
            break
    if g[i] == -1:
        if len(f[ord(t[i])-97]) == 0:
            print(-1)
            sys.exit()
        g[i] = f[ord(t[i])-97][0]
    if g[i] <= g[i-1]:
        cnt += 1
    
print(cnt*len(s)+g[-1]+1)
    




### FIXED CODE ###

import sys
input = sys.stdin.readline

import bisect

s = input().split() 
s = list(s[0])
t = input().split() 
t = list(t[0])
f = [[] for _ in range(26)]

for i in range(len(s)):
    f[ord(s[i])-97].append(i)

g = [-1 for _ in range(len(t))]
if len(f[ord(t[0])-97]) == 0:
    print(-1)
    sys.exit()
g[0] = f[ord(t[0])-97][0]
cnt = 0
for i in range(1,len(t)):
    if len(f[ord(t[i])-97]) == 0:
        print(-1)
        sys.exit()

    if f[ord(t[i])-97][-1] > g[i-1]:
        index = bisect.bisect_right(f[ord(t[i])-97], g[i-1])
        g[i] = f[ord(t[i])-97][index]
    else:
        g[i] = f[ord(t[i])-97][0]
    if g[i] <= g[i-1]:
        cnt += 1

print(cnt*len(s)+g[-1]+1)
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(sorted(input()))
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = sorted([sorted(input()) for i in range(n)])
a = []
last = s[0]
count = 1
for i in range(1, n):
    if s[i] == last:
        count += 1
    else:
        a.append(count)
        count = 1
    last = s[i]
a.append(count)
ans = 0
for i in a:
    if i > 1:
        ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

import numpy as np


def solve(N, K, P, L):
    ans = np.iinfo(np.int64).min

    for i in range(N):
        score_acc = np.array([L[i]], dtype=np.int64)
        cur = P[i] - 1
        while cur != i:
            score_acc = np.append(score_acc, [L[cur]])
            cur = P[cur] - 1
        score_acc = np.cumsum(score_acc)
        M = len(score_acc)
        if M < K and score_acc[-1] > 0:
            res = K // M * score_acc[-1]
            if K % M:
                res += max(score_acc[: K % M])
            else:
                res += -score_acc[-1] + max(score_acc)
            ans = max(ans, res)
        else:
            res = max(score_acc[:K])
            ans = max(ans, res)
    return ans


N, K = map(int, input().split())
P = np.array(input().split(), dtype=np.int32)
L = np.array(input().split(), dtype=np.int32)
print(solve(N, K, P, L))


### FIXED CODE ###

from itertools import accumulate


def solve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    L = list(map(int, input().split()))

    ans = -float("inf")
    for i in range(N):
        score_acc = [L[i]]
        cur = P[i] - 1
        while cur != i:
            score_acc.append(L[cur])
            cur = P[cur] - 1
        score_acc = list(accumulate(score_acc))
        M = len(score_acc)
        if M < K and score_acc[-1] > 0:
            res = K // M * score_acc[-1]
            if K % M:
                res += max(score_acc[: K % M])
            else:
                res += -score_acc[-1] + max(score_acc)
            ans = max(ans, res)
        else:
            res = max(score_acc[:K])
            ans = max(ans, res)
    return ans


print(solve())
### BUGGY CODE ###

l, r = list(map(int, input().split()))
# if r-l >=2019:
# 	print(0)
# else:
x= [i*j%2019 for i in range(l,r) for j in range (i+1,r+1)]
x.sort()
print(x[0])

### FIXED CODE ###

l, r = list(map(int, input().split()))
if r-l >=2019:
	print(0)
else:
	x= [i*j%2019 for i in range(l,r) for j in range (i+1,r+1)]
	x.sort()
	print(x[0])
### BUGGY CODE ###

n, c, k = map(int, input().split())
tList = [int(input()) for _ in range(n)]
tList.sort()
count = 0
while 1:
    limit = tList[0] + k
    for i in range(min(c, len(tList))):
        mark = i
        if tList[i] > limit:
            mark -= 1
            break
    count += 1
    tList = tList[mark + 1:]
    if tList == []:
        break
print(count)

### FIXED CODE ###

def boundary_find(array, limit):
    ceil = len(array) - 1 
    floor = 0
    while 1:
        center = (ceil + floor) // 2
        if array[center] <= limit:
            floor = center
        else:
            ceil = center
        if ceil - floor == 1:
            break
    return ceil

n, c, k = map(int, input().split())
tList = [int(input()) for _ in range(n)]
tList.sort()
count = 0
first = 0
while 1:
    limit = tList[first] + k
    last = min(first + c, n)
    if tList[last - 1] <= limit:
        mark = last
    else:
        mark = boundary_find(tList, limit)
    count += 1
    first = mark
    if first == n:
        break
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    h, w = input_to_int_map()
    zone = [[s for s in input()] for i in range(h)]

    from collections import deque
    black_cell = deque()

    black_distance = [[0] * w for i in range(h)]
    for i, row in enumerate(zone):
        for j, cell in enumerate(row):
            if cell == "#":
                black_cell.append((i, j))

    while black_cell:
        black_h, black_w = black_cell.popleft()
        pre_black_distance = black_distance[black_h][black_w]
        for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            move_h = black_h + i
            move_w = black_w + j
            if move_h < 0 or move_w < 0 or move_h >= h or move_w >= w:
                continue
            if zone[move_h][move_w] == ".":
                black_distance[move_h][move_w] = pre_black_distance + 1
                black_cell.append((move_h, move_w))
                zone[move_h][move_w] = "#"

    return max(list(map(max, black_distance)))


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

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

li = [0] * (N - K + 1)

max = max(P)
dict = {}
sumList = [0] * max

sumList[0] = 1
dict[1] = 1

for i in range(1, max):
    sumList[i] = sumList[i - 1] + (i + 1)
    dict[i+1] = sumList[i] / (i + 1)

#一番大きな数を含む並び順を求める
for i in range(N - K + 1):
    for j in range(K):
        #期待値を計算してなかったら、計算
#        if(dict.get(P[i + j], -1) == -1):
#            tmp = 0
#            p = P[i + j]
#            for k in range(1, p + 1):
#                tmp = tmp + (k / p)
#            dict[p] = tmp

        li[i] = li[i] + dict.get(P[i + j])

#print(dict)
#print(sumList)
print(sorted(li, reverse=True)[0])

### FIXED CODE ###

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

li = [0] * (N - K + 1)

max = max(P)
dict = {}
sumList = [0] * max

sumList[0] = 1
dict[1] = 1

for i in range(1, max):
    sumList[i] = sumList[i - 1] + (i + 1)
    dict[i+1] = sumList[i] / (i + 1)

for i in range(K):
    li[0] = li[0] + dict.get(P[i])

#一番大きな数を含む並び順を求める
for i in range(1, N - K + 1):
    li[i] = li[i - 1] - dict.get(P[i - 1]) + dict.get(P[i + K - 1])

#print(li)
print(sorted(li, reverse=True)[0])
### BUGGY CODE ###

import sys
from collections import deque
#input = sys.stdin.readline

def main():        
    h,w=map(int,input().split())
    s=[[]*w for _ in range(h)]
    for i in range(h):
        s[i]=list(input())
    chk=deque()
    d=[[0,1],[0,-1],[1,0],[-1,0]]

    def bfs(x,y):
        ans,dist=0,0
        a=[[-1]*w for _ in range(h)]
        chk.append([x,y,0])
        a[x][y]=0
        while chk:
            x,y,dist=chk.popleft()
            bx,by=x,y
            a[x][y]=dist
            for dx,dy in d:
                x=dx+bx
                y=dy+by
                if x>=0 and y>=0 and x<=h-1 and y<=w-1:
                    if s[x][y]=='.' and a[x][y]==-1:
                        chk.append([x,y,dist+1])
        ans=0
        for i in range(h):
            for j in range(w):
                ans=max(ans,a[i][j])
        return ans
    
    ans=0
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                continue
            ans=max(ans,bfs(i,j))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import heapq
from collections import deque
input = sys.stdin.readline

def main():        
    h,w=map(int,input().split())
    s=[input() for _ in range(h)]

    def bfs(x,y):
        dist=[[-1]*w  for _ in range(h)]
        seen=[[False]*w for _ in range(h)]
        stk=[(x,y,0)]
        while stk:
            px,py,dst=stk.pop(0)
            if seen[px][py]:
                continue
            seen[px][py]=True
            
            if s[px][py]=='#':
                dist[px][py]=0
                continue
            
            for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:
                if px+x<0 or px+x>=h or py+y<0 or py+y>=w:
                    continue
                else:
                    stk.append((px+x,py+y,dst+1))
            dist[px][py]=dst
        ans=0
    
        for i in range(h):
            ans=max(max(dist[i]),ans)
        return ans
    
    ans=0
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                continue
            ans=max(ans,bfs(i,j))
    print(ans)

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

import sys
import numpy as np

N = int(input())
L = np.array(list(map(int, sys.stdin.readline().split())))
L = np.sort(L)

count = 0

for i in range(N - 2):
    a = L[i]
    for j in range(i + 1, N - 1):
        b = L[j]
        c_cand = L[j + 1:]
        c_num = np.count_nonzero((c_cand < a + b) & (a < b + c_cand) & (b < a + c_cand))
        count += c_num
        
print(count)

### FIXED CODE ###

import sys
import bisect

N = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().split()))
L.sort()

count = 0

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        c = bisect.bisect_left(L, L[i]+L[j])
        if c > j:
            count += c - j - 1
        else:
            pass
        
print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
sum = 0
for i in range(N-1):
    for j in range(i+1, N):
        sum += A[i] ^ A[j]
print(sum%1000000007)

### FIXED CODE ###

import numpy as np
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
A = np.array(A)

ans = 0
twopow = 1
for n in range(60):
    tmp = A & 1
    one = np.count_nonzero(tmp)
    zero = N - one
    ans = (ans + (one * zero) * twopow) % MOD
    A >>= 1
    twopow = twopow << 1 % MOD

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

n = int(input())
s = input()
a = []
for i in range(n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      a.append(s[i] + s[j] + s[k])
print(len(set(a)))

### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(10):
  idx1=s.find(str(i))
  for j in range(10):
    idx2=s.find(str(j),idx1+1,n)
    for k in range(10):
      idx3=s.find(str(k),idx2+1,n)
      if idx1==-1 or idx2==-1 or idx3==-1:
        continue
      else:
        ans+=1
print(ans)