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

n=int(input())
L=list(map(int, input().split()))
L.sort()
count = 0
for a in range(n-2):
  for b in range(a+1,n-1):
    if L[a] + L[b] > L[n-1]:
      count += n - b - 1
      continue
    left = b + 1
    right = n - 1
    while right - left > 0:
      c = (left+right) // 2
      if L[c] < L[a] + L[b]:
        left = c + 1
      else:
        right = c
    count += left - b - 1
print(count)

### FIXED CODE ###

n=int(input())
L=list(map(int, input().split()))
L.sort()
count = 0
for a in range(n-2):
  for b in range(a+1,n-1):
    if L[a] + L[b] > L[n-1]:
      count += n - b - 1
      continue
    left = b + 1
    right = n - 1
    while right - left > 0:
      c = (left+right) // 2
      if L[c] < L[a] + L[b]:
        left = c + 1
      else:
        right = c
    count += left - b - 1
print(count)
### BUGGY CODE ###

N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
mod = 10**9+7

dp = [[0]*(M+1) for i in range(N+1)]
dps = [[0]*(M+1) for i in range(N+1)]
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            dp[n+1][m+1] = (dps[n][m]+1)%mod
        dps[n+1][m+1] = (dp[n+1][m+1]+dps[n+1][m]+dps[n][m+1]-dps[n][m])%mod

print(dps[-1][-1]+1)


### FIXED CODE ###

n,m = map(int,input().split())
s = list(map(int,input().split()))
t = list(map(int,input().split()))
dp0 = [[0 for i in range(m+2)] for j in range(n+2)]
dp1 = [[0 for i in range(m+2)] for j in range(n+2)]
dp0[0][0] = 1
mod = 10**9+7
for i in range(n+1):
    for j in range(m+1):
        dp0[i+1][j] = (dp0[i+1][j]+dp0[i][j])%mod
        dp1[i][j] = (dp1[i][j]+dp0[i][j])%mod
        dp1[i][j+1] = (dp1[i][j+1]+dp1[i][j])%mod
        if i != n and j != m and s[i] == t[j]:
            dp0[i+1][j+1] = (dp1[i+1][j+1]+dp1[i][j])%mod
print(dp1[n][m])
### BUGGY CODE ###

import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))
    
dist = [[INF] * 3001 for i in range(n)]
dist[0][min(s, 3000)] = 0

q = [(0, min(s, 3000), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v][gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= 3000:
            if dist[v][tmp + cc] > dist[v][tmp] + dd:
                dist[v][tmp + cc] = dist[v][tmp] + dd
                r.append(tmp)
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v][g] + time < dist[nxt_v][g - cost]:
                dist[nxt_v][g - cost] = dist[v][g] + time
                heapq.heappush(q, (dist[nxt_v][g - cost], g - cost, nxt_v))

for i in range(1, n):
     print(min(dist[i]))


### FIXED CODE ###

import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
MAX_ = 2600

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))


dist = [INF] * ((MAX_ + 1) * n)
dist[min(s, MAX_)] = 0

q = [(0, min(s, MAX_), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * (MAX_ + 1) + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= MAX_:
            if dist[v * (MAX_ + 1) + tmp + cc] > dist[v * (MAX_ + 1) + tmp] + dd:
                dist[v * (MAX_ + 1) + tmp + cc] = dist[v * (MAX_ + 1) + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * (MAX_ + 1) + g] + time < dist[nxt_v * (MAX_ + 1) + g - cost]:
                dist[nxt_v * (MAX_ + 1) + g - cost] = dist[v * (MAX_ + 1) + g] + time
                heapq.heappush(q, (dist[nxt_v * (MAX_ + 1) + g - cost], g - cost, nxt_v))

for i in range(1, n):
     print(min(dist[i * (MAX_ + 1):(i + 1) * (MAX_ + 1)]))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
R = ''
for i in range(1,N+1,1):
  R += str(A.index(i)+1) + " "
print(R)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(range(1,N+1,1))
C = zip(A,B)
D = sorted(C)
a, b = zip(*D)
print(" ".join(str(x) for x in b))
### BUGGY CODE ###

def factorize(a):
    factors = {}
    v = a
    p = 2
    while p*p<=a:
        if v%p==0: factors[p] = 0
        while v%p==0:
            v//=p
            factors[p]+=1
        p+=1
    if v>1: factors[v] = 1
    return factors

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7

# calc lcm
lcm = {}
for a in A:
    factors_a = factorize(a)
    for k, v in factors_a.items():
        if k not in lcm or lcm[k]<v: lcm[k] = v

C = 1
for k, v in lcm.items():
    C *= pow(k, v, mod)
    C %= mod

ans = 0
for a in A:
    ans += C * pow(a, mod-2, mod)
    ans %= mod

print(ans)

### FIXED CODE ###

def factorize(a):
    factors = {}
    v = a
    if v%2==0: factors[2]=0
    while v%2==0:
        v//=2
        factors[2]+=1
    
    p = 3
    while p*p<=a:
        if v%p==0: factors[p] = 0
        while v%p==0:
            v//=p
            factors[p]+=1
        p+=2
    if v>1: factors[v] = 1
    return factors

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7

# calc lcm
lcm = {}
for a in A:
    factors_a = factorize(a)
    for k, v in factors_a.items():
        if k not in lcm or lcm[k]<v: lcm[k] = v

C = 1
for k, v in lcm.items():
    C *= pow(k, v, mod)
    C %= mod

ans = 0
for a in A:
    ans += C * pow(a, mod-2, mod)
    ans %= mod

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

n,m,r = map(int,input().split())
rl = list(map(int,input().split()))

d = [[float("inf") for i in range(n)] for j in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c


#d[i][j]は2頂点間i, j間の移動コストを格納, Vは頂点数
def warshall_floyd(d, V): 
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    return d #d[i][j]に頂点i, j間の最短距離を格納

d = warshall_floyd(d, n)
import itertools
ans = float("inf")
for balls in itertools.permutations(rl):
    a = 0
    for i in range(r-1):
        a += d[balls[i]-1][balls[i+1]-1]
    ans = min(ans, a)

print(ans)

### FIXED CODE ###

n,m,r = map(int,input().split())
rl = list(map(int,input().split()))

d = [[float("inf") for i in range(n)] for j in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c


#d[i][j]は2頂点間i, j間の移動コストを格納, Vは頂点数
def warshall_floyd(d, V): 
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    return d #d[i][j]に頂点i, j間の最短距離を格納

d = warshall_floyd(d, n)
import itertools
ans = float("inf")
for balls in itertools.permutations(rl):
    a = 0
    for i in range(r-1):
        a += d[balls[i]-1][balls[i+1]-1]
    ans = min(ans, a)

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

ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
iix = lambda x:list(int(input()) for _ in range(x))
mix = lambda x:list(li() for _ in range(x))
##########
def main(n,k,q,a):
    point = [k]*n
    for ans in a:
        point = answer(ans-1, point)
    for i in range(len(point)):
        print(judge(point[i]))
    
def answer(n,point):
    for i in range(len(point)):
        if i != n : point[i] -= 1
    return point
 
def judge(p):
    return "Yes" if p > 0 else "No"
 
n,k,q = mi()
a = iix(q)
main(n,k,q,a)

### FIXED CODE ###

from collections import Counter as counter

ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
iix = lambda x:list(int(input()) for _ in range(x))
mix = lambda x:list(li() for _ in range(x))
##########
def main(n,k,q,a):
    c = counter(a)
    for i in range(1,n+1):
        print("Yes" if k-q+c[i] > 0 else "No")

n,k,q = mi()
a = iix(q)
main(n,k,q,a)
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    AB = [tuple(map(int, ab)) for ab in map(str.split, args[1:1+m])]
    CD = [tuple(map(int, cd)) for cd in map(str.split, args[1+m:1+m+k])]

    friends = [set() for _ in range(n+1)]
    blocked = [set() for _ in range(n+1)]

    for a, b in AB:
        friends[a].add(b)
        friends[b].add(a)

    for c, d in CD:
        blocked[c].add(d)
        blocked[d].add(c)

    ret = [0]*(n+1)
    checked = set()
    for a in range(1, n+1):
        if a in checked:
            continue
        connected = set()
        stack = list(friends[a])
        while stack:
            b = stack.pop()
            checked.add(b)
            connected.add(b)
            stack.extend(friends[b]-checked)
        for i in connected:
            ret[i] += len(connected-friends[i]-blocked[i]) - 1

    return ' '.join(map(str, ret[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8
from sys import setrecursionlimit


def dfs(node: int):
    if checked[node]:
        return

    checked[node] = True
    chain.add(node)
    for n in friends[node]:
        dfs(n)


def solve(*args: str) -> str:
    setrecursionlimit(2 * 10 ** 9)
    n, m, k = map(int, args[0].split())

    global friends
    friends = {i: set() for i in range(n+1)}
    blocked = {i: set() for i in range(n+1)}

    for a, b in map(str.split, args[1:1+m]):
        friends[int(a)].add(int(b))
        friends[int(b)].add(int(a))

    for c, d in map(str.split, args[1+m:1+m+k]):
        blocked[int(c)].add(int(d))
        blocked[int(d)].add(int(c))

    global checked
    checked = [False]*(n+1)

    ret = [0]*(n+1)
    for a in range(1, n+1):
        if checked[a]:
            continue

        global chain
        chain = set()
        dfs(a)
        count = len(chain) - 1
        for i in chain:
            ret[i] += count - len(chain & (friends[i] | blocked[i]))

    return ' '.join(map(str, ret[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
H.sort(reverse=True)
if len(H)<=K:
    a=0
else:
    for i in range(K):
        H.pop(0)
    a=sum(H)
print(a)

### FIXED CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
H.sort(reverse=True)
if len(H)<=K:
    a=0
else:
    a=sum(H[K:])
print(a)
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = N
for i in range(N):
    ans=min(ans,S[i+1:].count('E')+S[:i].count('W'))
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
e=S[1:].count('E')
w=S[:0].count('W')
ans = e+w
for i in range(1,N):
    if(S[i]=='E'):
        e=e-1
    if(S[i-1]=='W'):
        w=w+1
    ans=min(ans,e+w)
print(ans)
### BUGGY CODE ###

import numpy as np
from collections import deque

S = input()
Q = int(input())
reverse_cnt = 1
index = []
s = deque([])

for i in range(Q):
    query = input().split()
    if query[0] == "1":
        reverse_cnt *= -1
        index = list(np.array(index) * -1)
    else:
        s.append(query[2])
        if query[1] == "1":
            index.append(-1)
        else:
            index.append(1)

if reverse_cnt == -1:
    S = S[::-1]

insert = ""
add = ""

for i in index:
    if i == 1:
        add += s.popleft()
    elif i == -1:
        insert += s.popleft()

print(insert[::-1] + S + add)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
reverse_cnt = 0
s = deque([i for i in S])

for i in range(Q):
    query = input().split()
    if query[0] == "1":
        reverse_cnt += 1
    else:
        if query[1] == "1":
            if reverse_cnt % 2 == 0:
                s.appendleft(query[2])
            else:
                s.append(query[2])
        else:
            if reverse_cnt % 2 == 0:
                s.append(query[2])
            else:
                s.appendleft(query[2])

if reverse_cnt % 2 == 0:
    while s:
        print(s.popleft(), end="")
else:
     while s:
        print(s.pop(), end="")
### BUGGY CODE ###

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

def main():
    flag = 0
    for i in range(len(A)-1):
        for j in range(i+1, len(A)):
            if A[i] == A[j]:
                flag = 1
                break
            else:
                continue
       

    if flag == 0:
        print('YES')
    else:
        print('NO')


if __name__ == "__main__":
    main()
    

### FIXED CODE ###

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

def main():
    flag = 0
    new_A = sorted(A)

    for i in range(S-1):
        if new_A[i] == new_A[i+1]:
            flag = 1
            break
        else:
            continue

    if flag == 0:
        print('YES')
    else:
        print('NO')


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

from collections import defaultdict

N,M,Q = map(int, input().split())

X = [[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
    l,r = map(int, input().split())
    X[l-1][r-1] += 1

query = [tuple(map(int, input().split())) for _ in range(Q)]

"""
C[i][j]：iから出発してjまで（ｊを含む）のどこかに行くもの
C[i][j] = X[i][i] + X[i][i+1] + ... + X[i][j-1] + X[i][j]
"""
C =  [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if X[i][j] != 0:
            #if j == i
            C[i][j] = C[i][j-1] + X[i][j]
        else:
            C[i][j] = C[i][j-1]
            
"""
print("---------------")
for a in C:
    print(a)
"""

for p,q in query:
    cnt = 0
    for r in range(p-1,q):
        cnt += C[r][q-1]
    print(cnt)

### FIXED CODE ###


def main():
    N,M,Q = map(int, input().split())

    X = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(M):
        l,r = map(int, input().split())
        X[l-1][r-1] += 1

    query = [tuple(map(int, input().split())) for _ in range(Q)]

    """
    C[i][j]：iから出発してjまで（ｊを含む）のどこかに行くもの
    C[i][j] = X[i][i] + X[i][i+1] + ... + X[i][j-1] + X[i][j]
    """
    C =  [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            C[i][j] = C[i][j-1] + X[i][j]


    """
    print("---------------")
    for a in C:
        print(a)
    """

    for p,q in query:
        cnt = 0
        for r in range(p-1,q):
            cnt += C[r][q-1]
        print(cnt)


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

N=int(input())
S=input()
a=S.count('R')
b=S.count('G')
c=S.count('B')
ans=a*b*c
for i in range(N-2):
  for j in range(i+1,N-1):
    if S[i]!=S[j]:
      if (2*j-i)<=N-1:
        if S[i]!=S[2*j-i]!=S[j]:
          ans-=1
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
a=S.count('R')
b=S.count('G')
c=S.count('B')
ans=a*b*c
for i in range(N-2):
  for j in range(i+1,N-1):
    if S[i]!=S[j]:
      if (2*j-i)<=N-1 and S[i]!=S[2*j-i]!=S[j]:
        ans-=1     
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = input().split()

ans = {}
for x in set(A):
    t = 0
    for y in set(A):
        m = A.count(y) if x != y else A.count(y) - 1
        t += m * (m - 1) // 2
    ans[x] = t

for x in A:
    print(ans[x])


### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline

N = int(input())
A = input().split()
a = Counter(A)

ans_all = 0
for x in a.keys():
    m = a[x]
    ans_all += m * (m - 1) // 2

for x in A:
    m = a[x] - 1
    print(ans_all - m)
### BUGGY CODE ###

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


m = [0]*(10**6 + 1)

for i in a:
    if m[i] == 1:
        m[i] = 2
        continue
    tmp = i 
    while tmp <= 10**6:
        m[tmp] += 1
        tmp += i
ans = 0
for i in a:
    if m[i] == 1:
        ans += 1
print(ans)

### FIXED CODE ###

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

ma = max(a)
m = [0]*(ma + 1)

for i in a:
    if m[i] == 1:
        m[i] = 2
        continue
    for j in range(i,ma+1,i):
        m[j]+=1
ans = 0
for i in a:
    if m[i] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())
ans = 0
for i in range(1,n):
    ans += -(-len(make_divisors(i)))
print(ans)

### FIXED CODE ###

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

n=int(input())

S=[''.join(sorted(input())) for _ in range(n)]

ans=0

for i in range(n-1):
    for j in range(i+1,n):
        if S[i]==S[j]:
            ans+=1
print(ans)        

### FIXED CODE ###

import collections
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


n=int(input())

S=[''.join(sorted(input())) for _ in range(n)]

c=collections.Counter(S)
ans=0
for i in c.values():
    if i==2:
        ans+=1
    elif i>2:
        ans+=cmb(i,2)
print(ans)
### BUGGY CODE ###

from re import *
n=int(input())
s=input()
l=["0","1","2","3","4","5","6","7","8","9"]
ans=0
for i in l:
    for j in l:
        for k in l:
            if match(".*{}.*{}.*{}".format(i,j,k),s):
                ans+=1
print(ans)

### FIXED CODE ###

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

ans = 0

for i in range(10):
    a = s.find(str(i))
    if a == -1:
        continue
    for j in range(10):
        b = s.find(str(j), a + 1)
        if b == -1:
            continue
        for k in range(10):
            c = s.find(str(k), b + 1)
            if c == -1:
                continue
            ans += 1
print(ans)
### BUGGY CODE ###

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

def Maze_Master(y, x, c):
    if y < 0 or y > h-1 or x < 0 or x > w-1 or m[y][x] != 0 and m[y][x] < c or s[y][x] == "#":
        pass
    else:
        m[y][x] = c
        c += 1
        Maze_Master(y+1, x, c)
        Maze_Master(y-1, x, c)
        Maze_Master(y, x+1, c)
        Maze_Master(y, x-1, c)
    return m
    
a = 0
for y in range(h):
    for x in range(w):
        m = [[0]*w for _ in range(h)]
        ans = Maze_Master(y, x, 1)
        l = []
        for i in ans:
            l.append(max(i))
        b = max(l)
        a = max(a, b)

print(a-1)

### FIXED CODE ###

import queue

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

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            t = [["."]*w for _ in range(h)]
            t[i][j] = 0
            q = queue.Queue()
            q.put((j, i))
            while True:
                x, y = q.get()
                for k, l in (1, 0), (-1, 0), (0, 1), (0, -1):
                    if (0 <= x+k and x+k < w and
                        0 <= y+l and y+l < h and
                        s[y+l][x+k] == "." and t[y+l][x+k] == "."):
                            t[y+l][x+k] = t[y][x] + 1
                            q.put((x+k, y+l))
                            
                if q.empty():
                    ans = max(ans, t[y][x])
                    break
print(ans)
### BUGGY CODE ###

import fractions
def main():
    T1, T2 = map(int, input().split())
    f = fractions.gcd(T1, T2)
    T1 //= f
    T2 //= f
    A1, A2 = map(int, input().split())
    B1, B2 = map(int, input().split())
    f = fractions.gcd(fractions.gcd(A1, A2), fractions.gcd(B1, B2))
    A1 //= f
    A2 //= f
    B1 //= f
    B2 //= f

    a_half = T1*A1
    a_full = a_half + T2*A2
    b_half = T1*B1
    b_full = b_half + T2*B2

    if a_full == b_full:
        print("infinity")
        return
    elif a_full > b_full:
        flg = 1
    else:
        flg = -1

    if flg == 1 and a_half <= b_half:
        ans = 1
    elif flg == -1 and a_half >= b_half:
        ans = 1
    else:
        ans = 0

    a = a_full
    b = b_full
    while True:
        if flg == 1 and a + a_half < b + b_half:
            ans += 2
        elif flg == -1 and a + a_half > b + b_half:
            ans += 2
        elif a + a_half == b + b_half:
            ans += 1
        else:
            break
        a += a_full
        b += b_full

    print(ans)

main()


### FIXED CODE ###

import fractions
def main():
    T1, T2 = map(int, input().split())
    f = fractions.gcd(T1, T2)
    T1 //= f
    T2 //= f
    A1, A2 = map(int, input().split())
    B1, B2 = map(int, input().split())
    f = fractions.gcd(fractions.gcd(A1, A2), fractions.gcd(B1, B2))
    A1 //= f
    A2 //= f
    B1 //= f
    B2 //= f

    dif_half = T1*A1 - T1*B1
    dif_full = T1*A1 + T2*A2 - T1*B1 - T2*B2

    if dif_full == 0 or A1 == B1:
        print("infinity")
        return
    elif dif_full * dif_half > 0:   # 増減が入れ替わらない場合は会うことはない
        print(0)
        return
    elif dif_full > 0:
        flg = 1
    else:
        flg = -1

    if flg == 1 and dif_half <= 0:
        ans = 1
    elif flg == -1 and dif_half >= 0:
        ans = 1
    else:
        ans = 0

    ans += (- dif_half // dif_full) * 2 - (- dif_half % dif_full == 0)

    print(ans)

main()
### BUGGY CODE ###

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

if 0 in A:
    print(0)
else:
    out = 1
    for a in A:
        out *= a
    out = -1 if (out > 10 ** 18) else out
    print(out)


### FIXED CODE ###

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

if 0 in A:
    print(0)
else:
    out = 1
    for a in A:
        out *= a
        if out > 10 ** 18:
            out = -1
            break
    print(out)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 標準入力を取得
N = int(input())
S = input()

# 求解処理
ans = 0
for n in range(1000):
    V = str(n).zfill(3)
    f = 0
    for j in range(N):
        if S[j] == V[f]:
            f += 1
        if f == 3:
            break
    ans += (f == 3)

# 結果出力
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 標準入力を取得
N = int(input())
S = input()

# 求解処理
ans = 0
x_bit = [False for n in range(10)]
for x in range(N):
    S_x = int(S[x])
    if x_bit[S_x]:
        continue
    x_bit[S_x] = True
    y_bit = [False for n in range(10)]
    for y in range(x + 1, N):
        S_y = int(S[y])
        if y_bit[S_y]:
            continue
        y_bit[S_y] = True
        z_bit = [False for n in range(10)]
        for z in range(y + 1, N):
            S_z = int(S[z])
            if z_bit[S_z]:
                continue
            z_bit[S_z] = True
            ans += 1

# 結果出力
print(ans)
### BUGGY CODE ###

w=list(input())
now=0
num=len(w)
w.append(" ")
count=0
while now<num:
  if w[now]!="A":
    now+=1
  else:
    if w[now+1]!="B":
      now+=1
    else:
      if w[now+2]!="C":
        now+=1
      else:
        w[now]="B"
        w[now+1]="C"
        w[now+2]="A"
        count+=1
        back=now-1
        b=True
        while back>0 and b==True:
          if w[back]!="A":
            b=False
          else:
            w[back]="B"
            w[back+1]="C"
            w[back+2]="A"
            count+=1
            back-=1
print(count)
            


### FIXED CODE ###

w=input()
count=0
num=len(w)
w1=""
w+=" "
while count<num:
  if w[count]=="A":
    w1+="A"
    count+=1
  elif w[count]=="B":
    if w[count+1]=="C":
      w1+="D"
      count+=2
    else:
      w1+="B"
      count+=1
  else:
    w1+="C"
    count+=1
counta=0
ans=0
num=len(w1)
for i in range(num):
  if w1[i]=="A":
    counta+=1
  elif w1[i]=="D":
    ans+=counta
  else:
    counta=0
print(ans)