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

N, M, Q = map(int, input().split())  # N個の駅, M本の列車, Q個のクエリ
# 始点と終点を全て格納する
X = [[0]*501 for _ in range(501)]
# 累積和を取るための二次元リスト(累積和自体は一次元, 最後に縦方向に和を取る)
C = [[0]*501 for _ in range(501)]

for _ in range(M):
    left, right = map(lambda x: int(x)-1, input().split())
    X[left][right] += 1  # 始点と終点を全て格納する

# 横方向に累積和を取る
for i in range(N):
    for j in range(N):
        C[i][j] = C[i][j-1] + X[i][j]

for _ in range(Q):
    p, q = map(lambda x: int(x)-1, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += C[i][q] - C[i][p-1]
    print(ans)


### FIXED CODE ###

N, M, Q = map(int, input().split())  # N個の駅, M本の電車, Q個のクエリ
X = [[0]*501 for _ in range(501)]
C = [[0]*501 for _ in range(501)]
for _ in range(M):
    left, right = map(lambda x: int(x)-1, input().split())
    X[left][right] += 1

for i in range(N):
    for j in range(N):
        # 累積和
        C[i][j] = C[i][j-1] + X[i][j]  # 横方向に累積されていく
for _ in range(Q):
    p, q = map(lambda x: int(x)-1, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += C[i][q] - C[i][p-1]
    print(ans)
### BUGGY CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import itertools
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N,K = MI()

A = LI()

multi = {}
for j in range(K, N+1):
    target = A[j-K:j]
    ans = 1
    for t in target:
        ans = ans * t
    multi[j] = ans

for i in range(K, N+1):
    if i-1 in multi:
        if multi[i] > multi[i-1]:
            print("Yes")
        else:
            print("No")

### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import itertools
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N,K = MI()

A = LI()

for j in range(K, N+1):
    if j == K:
        continue
    if A[j-K-1] < A[j-1]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from numba import njit, int32, int64
from numba.typed import Dict

@njit
def solve(B):
    A = Dict.empty(
        key_type=int64,
        value_type=int64)
    for b in B:
      A[b] = A.get(b, 0) + 1
    r = 0
    if 1 in A:
        if A[1] == 1:
            return 1
        return 0
    for a, v in A.items():
        if v > 1:
            continue
        i = 2
        while i * i <= a:
            if a % i == 0:
                if i in A:
                    break
                if a // i in A:
                    break
            i += 1
        else:
            r += 1
    return r

def main():
    N = int(input())
    A = list(map(int, input().split()))
    return solve(A)

print(main())



### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    dp = [False] * (A[-1] + 1)
    r = 0

    for i, a in enumerate(A):
        if dp[a]:
            continue
        dp[a::a] = [True] * len(dp[a::a])
        if i < N - 1 and A[i + 1] == a:
            continue
        r += 1
    return r


print(main())
### BUGGY CODE ###

N = int(input())
S_list =[]
for _ in range(N):
  s = input()
  s = sorted(list(s))
  S_list.append(s)
counter = 0
for i in range(len(S_list)):
  for j in range(len(S_list)-1-i):
    if S_list[i] == S_list[i+j+1]:
      counter += 1
print(counter)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
dic={}
sum=0
for i in range(N):
    s=list(input())
    s.sort()
    s = "".join(s)
    if s in dic:
        sum+=dic[s]
        dic[s]+=1
    else:
        dic[s]=1
print(sum)
### BUGGY CODE ###

h, n = (int(x) for x in input().split())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
dp = [float('inf')] * (h)
for a, b in ab:
    for i in range(h):
        if i < a:
            if dp[i] > b:
                dp[i] = b
        else:
            if dp[i] > dp[i - a] + b:
                dp[i] =  dp[i - a] + b
print(dp[h - 1])

### FIXED CODE ###

h, n = (int(x) for x in input().split())
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
max_a = max(a for a, _ in ab)
dp = [0] * (h + max_a)
for i in range(1, h + 1):
    dp[i] = min(dp[i - a] + b for a, b in ab)
print(dp[h])
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
cnt = 0
for i in A:
    a, b, c = A.count(i), A.count(i+1), A.count(i+2)
    sums = a+b+c
    if sums > cnt:
        cnt = sums
print(cnt)

### FIXED CODE ###

from collections import Counter 
N = int(input())
A = Counter(list(map(int, input().split())))
cnt = 0
for i in A:
    sums = A[i] + A[i+1] + A[i+2]
    if sums > cnt:
        cnt = sums
print(cnt)
### BUGGY CODE ###

import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]
## math
DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y
from collections import defaultdict

def main():
    n, p = MII()
    s = IS()
    if 10%p == 0: # pが2または5の場合
        cnt = 0
        for i, si in enumerate(s):
            if int(si)%p == 0:
                cnt += i+1
        print(cnt)
        return None

    d = defaultdict(lambda: 0)
    d[0] = 1
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*int(si)
        ss %= p
        d[ss] += 1
        x = 10*x
    cnt = 0
    for dv in d.values():
        cnt += dv*(dv-1)//2
    print(cnt)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]
## math
DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y

def main():
    n, p = MII()
    s = list(map(int, IS()))
    if 10%p == 0: # pが2または5の場合
        cnt = 0
        for i, si in enumerate(s):
            if si%p == 0:
                cnt += i+1
        print(cnt)
        return None

    d = {i: 0 for i in range(p)}
    d[0] = 1
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*si
        ss %= p
        d[ss] += 1
        x = 10*x%p
    cnt = 0
    for dv in d.values():
        cnt += dv*(dv-1)//2
    print(cnt)


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

s = input()
S = len(s)

mod = 10**9+7

#全ての余りを確認する
dp = [[0 for i in range(13)]for j in range(S)]

if s[0] == "?":
    for i in range(10):
        dp[0][i%13] += 1
else:
    dp[0][int(s[0])%13] += 1

for i in range(1,S):
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(10*k+j)%13] += dp[i-1][k]%mod
    else:
        for k in range(13):
            dp[i][(10*k+int(s[i]))%13] += dp[i-1][k]%mod
            
print(dp[-1][5]%mod)

### FIXED CODE ###

s = input()
S = len(s)

mod = 10**9+7

#全ての余りを確認する
dp = [[0 for i in range(13)]for j in range(S)]

if s[0] == "?":
    for i in range(10):
        dp[0][i%13] += 1
else:
    dp[0][int(s[0])%13] += 1

for i in range(1,S):
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(10*k+j)%13] += dp[i-1][k]%mod
    else:
        for k in range(13):
            dp[i][(10*k+int(s[i]))%13] += dp[i-1][k]%mod
            
print(dp[-1][5]%mod)
### BUGGY CODE ###

#E_Picking Goods
R,C,K = map(int,input().split())
A =     [[0  for j in range(C)] for i in range(R)]
varr = [[[0  for j in range(C)] for i in range(R)] for k in range(4)]

for inputk in range(K):
    r,c,v = map(int,input().split())
    A[r-1][c-1] = v

for i in range(R):  
    for j in range(C):
        for k in range(2,-1,-1):
            if varr[k][i][j] >= 0:
                if  varr[k+1][i][j] < varr[k][i][j] + A[i][j]:
                    varr[k+1][i][j] = varr[k][i][j] + A[i][j]
        for kk in range(0,4):
            if varr[kk][i][j] >= 0:
                if i +1 < R :
                    if  varr[0][i + 1][j] < varr[kk][i][j]:
                        varr[0][i + 1][j] = varr[kk][i][j] 
                if j +1 < C :
                    if  varr[kk][i][j + 1] < varr[kk][i][j]:
                        varr[kk][i][j + 1] = varr[kk][i][j] 
ans = 0
for k in range (4):
    if ans < varr[k][R-1][C-1]:
        ans = varr[k][R-1][C-1]

print(ans)


### FIXED CODE ###

#E_Picking Goods
R,C,K = map(int,input().split())
A =     [[0  for j in range(C)] for i in range(R)]
varr = [[[0  for j in range(C)] for i in range(R)] for k in range(4)]

for inputk in range(K):
    r,c,v = map(int,input().split())
    A[r-1][c-1] = v

for i in range(R):  
    for j in range(C):
        for k in range(2,-1,-1):
            if varr[k][i][j] >= 0:
                if  varr[k+1][i][j] < varr[k][i][j] + A[i][j]:
                    varr[k+1][i][j] = varr[k][i][j] + A[i][j]
        for kk in range(0,4):
            if varr[kk][i][j] >= 0:
                if i +1 < R :
                    if  varr[0][i + 1][j] < varr[kk][i][j]:
                        varr[0][i + 1][j] = varr[kk][i][j] 
                if j +1 < C :
                    if  varr[kk][i][j + 1] < varr[kk][i][j]:
                        varr[kk][i][j + 1] = varr[kk][i][j] 
ans = 0
for k in range (4):
    if ans < varr[k][R-1][C-1]:
        ans = varr[k][R-1][C-1]

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

n, m = map(int, input().split())
broken = []
for _ in range(m):
    a = int(input())
    broken.append(a)
    
dp = [0]*(n+2)
mod = 1000000007
dp[n] = 1

for i in range(n-1,-1 , -1):
    if i in broken:
        dp[i] = 0
    else:
        dp[i] = dp[i+1] + dp[i+2]
print(dp[0]%mod)
    

### FIXED CODE ###

n, m = map(int, input().split())
broken=set(int(input()) for _ in range(m))    

dp = [0]*(n+2)
mod = 1000000007
dp[n] = 1

for i in range(n-1,-1 , -1):
    if i in broken:
        continue
    else:
        dp[i] = dp[i+1] + dp[i+2]
print(dp[0]%mod)
### BUGGY CODE ###

N,A,B,C,D = map(int,input().split())
S = input()

def test(x,y):
  # xからyへ行ける
  x -= 1
  y -= 1
  while x < y:
    if S[x+1] == '.':
      x += 1
      continue
    if S[x+2] == '.':
      x += 2
      continue
  return (x == y)

bl = test(A,C) and test(B,D)
if C > D:
  # 追い越す必要がある
  # 道の存在は保証されているので、局所的に詰まないようにBを配置できればよい
  can_swap = False
  for b in range(B-1,D):
    if S[b] == '#':
      continue
    if S[b-1] == '.' and S[b+1] == '.':
      can_swap = True
      break
  bl = bl and can_swap
answer = 'Yes' if bl else 'No'
print(answer)

### FIXED CODE ###

N,A,B,C,D = map(int,input().split())
S = input()

def test(x,y):
  # xからyへ行ける
  substr = S[x:y-1]
  return substr.find('##') == -1

bl = test(A,C) and test(B,D)
if C > D:
  # 追い越す必要がある
  # 道の存在は保証されているので、局所的に詰まないようにBを配置できればよい
  can_swap = False
  for b in range(B-1,D):
    if S[b] == '#':
      continue
    if S[b-1] == '.' and S[b+1] == '.':
      can_swap = True
      break
  bl = bl and can_swap
answer = 'Yes' if bl else 'No'
print(answer)
### BUGGY CODE ###

def knight(x, y):
    mod = 10 ** 9 + 7
    x, y = min(x, y), max(x, y)

    if (x + y) % 3 != 0:
        return 0
    if y > 2 * x:
        return 0

    move = (x + y) // 3
    right = 2 * move - y
    up = move-right

    ans = 1
    for i in range(1, move + 1):
        ans *= i
        ans %= mod
    for i in range(1, right + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    for i in range(1, up + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    return ans


if __name__ == "__main__":
    x, y = map(int, input().split())
    ans = knight(x, y)
    print(ans)


### FIXED CODE ###

def knight(x, y):
    mod = 10 ** 9 + 7
    x, y = min(x, y), max(x, y)

    if (x + y) % 3 != 0:
        return 0
    if y > 2 * x:
        return 0

    move = (x + y) // 3
    right = 2 * move - y
    up = move-right

    ans = 1
    for i in range(up):
        ans *= (move - i)
        ans *= pow(i + 1, mod - 2, mod)
        ans %= mod

    return ans


if __name__ == "__main__":
    x, y = map(int, input().split())
    ans = knight(x, y)
    print(ans)
### BUGGY CODE ###

import fractions as math
def main():
    A,B=map(int, input().split())
    gcd_ab = math.gcd(A,B)
    ans={1}
    i = 2
    while (A>1 and B>1) and (i <= gcd_ab):
        if A % i == 0 and B % i == 0:
            ans.add(i)
            A //= i
            B //= i
            gcd_ab = math.gcd(A,B)
        else:
            i += 1
    print(len(ans))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def main():
    A,B=map(int, input().split())
    ans = factorization(gcd(A,B))
    if ans[0][0] == 1:
        print(1)
    else:
        print(len(ans)+1)

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

import queue
n = int(input())
class Node:
    def __init__(self):
        self.nextNode = []
        self.checkNgo = -1
        self.group = -1
        
Nodes = [Node() for i in range(n)]
for i in range(n):
    s = input()
    for j in range(len(s)):
        if s[j] == '1':
            Nodes[i].nextNode.append(j)
            
def check(node,ngo):
    if node.checkNgo == -1:
        node.checkNgo = ngo
    elif node.checkNgo != ngo:
        return False
    elif node.checkNgo == ngo:
        return True
    for i in node.nextNode:
        if not check(Nodes[i],(ngo+1)%2):
            return False
    return True
    
if not check(Nodes[0],0):
    print(-1)
    exit(0)
    
def solv(nn):
    q = queue.Queue()
    q.put(Nodes[nn])
    Nodes[nn].group = 0
    while not q.empty():
        node = q.get()
        for i in node.nextNode:
            if Nodes[i].group != -1:
                Nodes[i].group = node.group+1
                q.put(Nodes[i])
    
def saidai():
    maxi = 0
    for i in range(n):
        maxi = max(Nodes[i].group,maxi)
    return maxi
    
kai = 0
for i in range(n):
    for j in range(n):
        Nodes[i].group = -1
    solv(i)
    kai = max(kai,saidai())
print(kai)

### FIXED CODE ###

import queue
import numpy as np
n = int(input())
class Node:
    def __init__(self):
        self.nextNode = []
        self.checkNgo = -1
        self.group = -1
        
Nodes = [Node() for i in range(n)]
for i in range(n):
    s = input()
    for j in range(len(s)):
        if s[j] == '1':
            Nodes[i].nextNode.append(j)
            
def check(node,ngo):
    if node.checkNgo == -1:
        node.checkNgo = ngo
    elif node.checkNgo != ngo:
        return False
    elif node.checkNgo == ngo:
        return True
    for i in node.nextNode:
        if not check(Nodes[i],(ngo+1)%2):
            return False
    return True
    
def ngoCheck():
    stack = [Nodes[0]]
    Nodes[0].checkNgo = 0
    while stack:
        node = stack.pop()
        for i in node.nextNode:
            if Nodes[i].checkNgo != -1 and Nodes[i].checkNgo == node.checkNgo:
                return False
            if Nodes[i].checkNgo == -1:
                Nodes[i].checkNgo = (node.checkNgo+1)%2
                stack.append(Nodes[i])
    return True
    
if not check(Nodes[0],0):
    print(-1)
    exit(0)
    
def solv():
    d = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if j in Nodes[i].nextNode:
                d[i][j] = 1
            else:
                d[i][j] = np.inf
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k]+d[k][j]:
                    d[i][j] = d[i][k]+d[k][j]
    return d
    
def saidai(d):
    maxi = 0
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            maxi = max(maxi,d[i][j])
    return maxi
    
d = solv()
print(saidai(d)+1)
### BUGGY CODE ###

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


from collections import defaultdict
import queue
connection = defaultdict(lambda: defaultdict(int))

for i in range(M):
  A, B = map(int, input().split())
  connection[A-1][B-1] = 1
  connection[B-1][A-1] = 1

c = defaultdict(int)
q = queue.Queue()
d = defaultdict(int)
p = defaultdict(int)

c[0] = 1
d[0] = 0
q.put(0)

while not(q.empty()):
  u = q.get()
  for v in range(N):
    if connection[u][v] == 1 and c[v] == 0:
      c[v] = 1
      d[v] = d[u] + 1
      p[v] = u
      q.put(v)
  c[u] = 2
print("Yes")
for i in range(1,N):
  print(p[i] + 1)

### FIXED CODE ###

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


from collections import defaultdict
import queue
connection = defaultdict(lambda: defaultdict(int))

for i in range(M):
  A, B = map(int, input().split())
  connection[A-1][B-1] = 1
  connection[B-1][A-1] = 1

c = defaultdict(int)
q = queue.Queue()
d = defaultdict(int)
p = defaultdict(int)

c[0] = 1
d[0] = 0
q.put(0)

while not(q.empty()):
  u = q.get()
  for v in connection[u]:
    if c[v] == 0:
      c[v] = 1
      d[v] = d[u] + 1
      p[v] = u
      q.put(v)
  c[u] = 2
print("Yes")
for i in range(1,N):
  print(p[i] + 1)
### BUGGY CODE ###

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

for i in range(N):
    A.append(input())

i = 0
while i< len(A):
    C = A.count(A[i])
    P = A[i]
    if(C > 1 and C % 2 == 0):
        for j in range(C):
            A.remove(P)
    elif(C > 1):
        for k in range(C- 1):
            A.remove(P)
        i+= 1
    else:
        i+= 1
    
print(len(A))

### FIXED CODE ###

N = int(input())
A = []
B = []
for i in range(N):
  A.append(int(input()))
  
A.sort()
B.append(1)

for i in range(1, N):
  if(A[i]!= A[i- 1]):
    B.append(1)
  else:
    B[-1]+= 1
  i+= 1
  
ans = list(filter(lambda x: x % 2 == 1, B))

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

N = int()
ans = 0
L = list(map(int, input().split()))
while True:
  for i in range(N):
    if L[i] % 2 == 0:
      L[i] = L[i] /2
    else:
      break
  ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
v = 0
cnt = 0
while v == 0:
    cnt += 1
    for i in range(N):
        if L[i] % 2 == 0:
            L[i] = L[i] // 2
        else:
            v += 1
print(cnt-1)
### BUGGY CODE ###

from collections import Counter

N = int(input())
A_array = list(map(int, input().split()))
Ai_dict = Counter(A_array)


def calc_comb(Ai_dict):
    num = 0
    for k,v in Ai_dict.items():
        num += v*(v-1)/2
    return int(num)


res_dict = dict([])

for n in A_array:
    if not n in res_dict.keys():
        res_dict[n] = calc_comb(Ai_dict) - Ai_dict[n]+1
    print(res_dict[n])


### FIXED CODE ###

from collections import Counter

N = int(input())
A_array = list(map(int, input().split()))
Ai_dict = Counter(A_array)


def calc_comb(dct):
    num = 0
    for k,v in dct.items():
        num += v*(v-1)/2
    return int(num)


res_dict = dict([])
TotalComb = calc_comb(Ai_dict)

for n in A_array:
    if not n in res_dict.keys():
        res_dict[n] = TotalComb - Ai_dict[n]+1
    print(res_dict[n])
### BUGGY CODE ###

def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)
    
    dp = [[0] * (M+1) for _ in range(N+1)]
    ans = [[''] * (M+1) for _ in range(N+1)]
    
    for i in range(1, N+1):
        p = S[i-1]
        for j in range(1, M+1):
            if T[j-1] == p:
                dp[i][j] = dp[i-1][j] + 1
                ans[i][j] = ans[i-1][j] + p
            else:
                if dp[i][j-1] < dp[i-1][j]:
                    dp[i][j] = dp[i-1][j]
                    ans[i][j] = ans[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
                    ans[i][j] = ans[i][j-1]
                
    print(ans[N][M])


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)
    dp = [[0] * (M+1) for _ in range(N+1)]
    
    for i in range(1, N+1):
        for j in range(1, M+1):
            p = (S[i-1] == T[j-1])
            dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + p)
            
    ans = []
    x, y = N, M
    while x and y:
        if dp[x][y] == dp[x-1][y]:
            x -= 1
        elif dp[x][y] == dp[x][y-1]:
            y -= 1
        else:
            x -= 1
            y -= 1
            ans.append(S[x])
        
    print(''.join(ans[::-1]))


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

def ri(): return int(input())
def rli(): return list(map(int, input().split()))

cnt=0
n=ri()
lu=rli()
lu.sort()
if n<=2:
  print(0)
else:
  for i in range(n-2):
    for j in range(i+1,n-1):
      r=n
      l=j
      if lu[-1]<lu[i]+lu[j]:
        cnt+=n-1-j
        continue
      if lu[j+1]>lu[j]+lu[i]:
        continue
      
      while r-l>1 :
        mid=(r+l)//2
        if lu[i]+lu[j]>lu[mid]:
          l=mid
        else:
          r=mid
      cnt+=l-j
  print(cnt)


### FIXED CODE ###

n=int(input())
l=sorted(map(int,input().split()))
from bisect import *
print(sum(bisect_left(l,l[i]+l[j])-i-1 for i in range(n) for j in range(i)))
### BUGGY CODE ###

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

def flatten(nested_list):
    return [e for inner_list in nested_list for e in inner_list]

N, K = map(int, raw_input().split())

a = [0] * N
b = [0] * N
ab = [[0, 0]] * N
for i in range(N):
    _a, _b = map(int, raw_input().split())
    ab[i] = [_a, _b]
ab.sort(key=lambda x:x[0])

ans = flatten([[a] * b for a, b in ab])
print ans[K - 1]


### FIXED CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, raw_input().split())

ab = [[0, 0]] * N
for i in range(N):
    _a, _b = map(int, raw_input().split())
    ab[i] = [_a, _b]
ab.sort(key=lambda x:x[0])

j = 0
index = 0
while j < K:
    j += ab[index][1]
    if j < K:
        index += 1

print ab[index][0]
### BUGGY CODE ###

n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())

max = a[1]-a[0]
for i in range(2,n):
    for j in range(0,i):
        tmp = a[i]-a[j]
        if max<tmp:
            max = tmp

print(max)



### FIXED CODE ###

n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())

max = a[1]-a[0]
min = a[0]
for i in range(1,n):
    if max < (a[i]-min):
        max = (a[i]-min)
    if min > a[i]:
        min = a[i]
        
print(max)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    tmp = input()
    if len(tmp) == 1:
        t = 1
        S = "".join(list(reversed(S)))
    else:
        t,f,c = tmp.split()
        f = int(f)
        if f == 1:
            S = c + S
        else:
            S = S + c
print(S)

### FIXED CODE ###

from collections import deque

S = input()
d = deque(S)
Q = int(input())
is_order = True
for i in range(Q):
    tmp = input()
    if len(tmp) == 1:
        t = 1
        is_order = not is_order
    else:
        t,f,c = tmp.split()
        f = int(f)
        if f == 1:
            if is_order:
                d.appendleft(c)
            else:
                d.append(c[::-1]) 
        else:
            if is_order:
                d.append(c)
            else:
                d.appendleft(c[::-1])
if is_order:
    print("".join(d))
else:
    print("".join(reversed(d)))