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

#D
from collections import deque
s = deque(input())
q = int(input())
for _ in range(q):
    t = list(map(str,input().split()))
    if t[0] == '1':
        s.reverse()
    else:
        if t[1] == "1":
            s.appendleft(t[2])
        else:
            s.append(t[2])
            
print("".join(s))

### FIXED CODE ###

#D
#import sys
#input = sys.stdin.readline
from collections import deque
s = deque(input())
q = int(input())
#flg:反転してるときtrue,してないときFalse
flg = False

for _ in range(q):
    t = tuple(map(str,input().split()))
    if t[0] == '1':
        if flg:
            flg = False
        else:
            flg = True
    else:
        if t[1] == "1" and flg == False:
            s.appendleft(t[2])
        elif t[1] == "1" and flg == True:
            s.append(t[2])
        elif t[1] == "2" and flg == False:
            s.append(t[2])
        else:
            s.appendleft(t[2])
 
    
if flg:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter,defaultdict
from operator import mul
from functools import reduce
def cmb1(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

def main():
    n=int(input())
    A=[int(_) for _ in input().split()]
    A_c=Counter(A)
    m=defaultdict(int)
    A_c_items=A_c.items()
    for i,a_c in enumerate(A_c_items):#選ぶ数字
        for j,a_c2 in enumerate(A_c_items):
            sum=0
            if i!=j and a_c2[1]>=2:
                sum+=cmb1(a_c2[1],2)
            elif i==j and a_c2[1]>=3:
                sum+=cmb1(a_c2[1]-1,2)
            m[a_c[0]]+=sum
    for i in range(n):
        print(m[A[i]])


if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter,defaultdict
from operator import mul
from functools import reduce
def cmb1(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

def main():
    n=int(input())
    A=[int(_) for _ in input().split()]
    A_c=Counter(A)

    combi=0
    for ac in A_c.items():
        if ac[1]>=2:
            combi+=cmb1(ac[1],2)
    for i in range(n):
        print(combi-(A_c[A[i]]-1))

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

N, M = map(int,input().split())
t = [[] for _ in range(N)]
visited = [0] * N
for _ in range(M):
    X, Y, Z = map(int,input().split())
    X -= 1
    Y -= 1
    t[X].append(Y)
    t[Y].append(X)
for i in range(1, 10 ** 5 + 1):
    s = visited.index(0)
    stack = [s]
    visited[s] = 1
    while stack:
        st = stack.pop()
        for to in t[st]:
            if visited[to]:
                continue
            visited[to] = 1
            stack.append(to)
    if sum(visited) == N:
        ans = i
        break
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

def dfs(s):
    if visited[s]:
        return
    visited[s] = 1
    for to in t[s]:
        if visited[to]:
            continue
        dfs(to)
    
N, M = map(int,input().split())
t = [[] for _ in range(N)]
visited = [0] * N
for _ in range(M):
    X, Y, Z = map(int,input().split())
    X -= 1
    Y -= 1
    t[X].append(Y)
    t[Y].append(X)
ans = 0
for i in range(0, N):
    if visited[i]:
        continue
    ans += 1
    dfs(i)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split(' '))
A = tuple(map(int, input().split(' ')))

mul = 1
for i in range(K):
    mul *= A[i]

pre = mul

for i in range(K, N):
    mul = pre
    mul //= A[i - K]
    mul *= A[i]
    if mul > pre:
        print('Yes')
    else:
        print('No')
    pre = mul


### FIXED CODE ###

N, K = map(int, input().split(' '))
A = tuple(map(int, input().split(' ')))

for i in range(K, N):
    if A[i] > A[i - K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N,K=input().split()
N,K=[int(N),int(K)]

while N >0:
  N=abs(N-K)
print(N)

### FIXED CODE ###

N,K=input().split()
N,K=[int(N),int(K)]

minimum=N%K
while N%K>K-N%K:
    minimum=K-N%K
    N=K-N%K
print(minimum)
### BUGGY CODE ###

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]

f = True
day = 1
while(f):
  if day > 10000:
    print(-1)
    sys.exit()
  done = set()
  nokori_games = 0
  
  for m in range(n):
    la = len(a[m])
    nokori_games += la
    if m in done:
      pass
    elif la:
      teki = a[m][0]
      jibun = m + 1
      if a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].popleft()
        a[teki - 1].popleft()
        done.add(m)
        done.add(teki - 1)
        nokori_games -= 1
      elif not len(a[teki - 1]):
        print(-1)
        sys.exit()
  if nokori_games:
    if not len(done):
      print(-1)
      sys.exit()
  else:
    print(day)
    sys.exit()
  day += 1


### FIXED CODE ###

import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()
### BUGGY CODE ###

from collections import defaultdict

ps = []
for i in range(2, 1000):
    is_p = True
    for j in range(2, i):
        if i % j == 0:
            is_p = False
            break
    if is_p:
        ps.append(i)

def factorization(n):
    arr = defaultdict(int)
    temp = n
    for i in ps:
        if i > int(-(-n**0.5//1))+1:
            break
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt
    if temp!=1:
        arr[temp] = 1
    if arr==[]:
        arr[n] = 1
    return arr


aa = defaultdict(int)

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

fs = [[]] * 1000001
for i in a:
    if not fs[i]:
        fs[i] = factorization(i)

for i in a:
    for k, v in fs[i].items():
        aa[k] = max(aa[k], v)


mod = 10 ** 9 + 7
ans = 0
for i in a:
    t = 1
    for k, v in aa.items():
        t = (t * k ** (v - fs[i][k])) % mod
    ans = (ans + t) % mod
print(ans)


### FIXED CODE ###

from collections import defaultdict

ps = []
for i in range(2, 1000):
    is_p = True
    for j in range(2, i):
        if i % j == 0:
            is_p = False
            break
    if is_p:
        ps.append(i)

def factorization(n):
    arr = defaultdict(int)
    temp = n
    for i in ps:
        if i > int(-(-n**0.5//1))+1:
            break
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt
    if temp!=1:
        arr[temp] = 1
    if arr==[]:
        arr[n] = 1
    return arr


aa = defaultdict(int)

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

fs = [[]] * 1000001
for i in a:
    if not fs[i]:
        fs[i] = factorization(i)

for i in a:
    for k, v in fs[i].items():
        aa[k] = max(aa[k], v)


mod = 10 ** 9 + 7
t = 1
for k, v in aa.items():
    t = (t * (k ** v)) % mod
ans = 0
for i in a:
    ans += t * pow(i, mod - 2, mod)
    ans %= mod
print(ans)
### BUGGY CODE ###

from collections import Counter



def main()->None:
    # a_iに１を足すか、１引くか、何もしないかの操作を行って、ある整数個数最大化をする
    # x を決めるとgreedyに決まる。
    # 最後の一つのサンプルがTLEになる。jit の使い方もよくわからん
    N = int(input())
    a = list(map(int, input().split()))
    a_dict = Counter(a)
    max_count = 0
    for key in a_dict.keys():
        tmp_count = 0
        for i in a_dict.keys():
            if abs(key - i) <= 1:
                tmp_count += a_dict[i]
        if tmp_count > max_count:
            max_count = tmp_count
    print(max_count)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def main()->None:
    N = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    max_a = max(a)
    # print(max_a)
    l = [0 for _ in range(max_a+2)] # 配列の初期化、固定長、位置が配列の数字で要素がカウント
    for i in a:
        l[i] += 1
    res = 0
    for i in range(0, max_a+1):
        tmp = l[i-1]+l[i]+l[i+1]
        res = max(res, tmp)
    print(res)


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

from bisect import bisect_left

N = int(input())
XD = [[int(i) for i in input().split()] for _ in range(N)]

mod = 998244353

XD.sort()

class SegTree:
  def __init__(self, n, v, f) :
    i = 1
    while i < n : 
      i <<= 1
    self.n = i
    self.v = v
    self.f = f
    self.tree = [v] * (i << 1)

  def update(self, i, x) :
    i += self.n - 1
    self.tree[i] = x
    while i > 0 :
      i = (i - 1) // 2
      self.tree[i] = self.f(self.tree[i * 2 + 1], self.tree[i * 2 + 2])

  # [l, r)
  def query(self, l, r) :
    l = l + self.n
    r = r + self.n
    s = self.v
    while l < r :
      if r & 1 :
        r -= 1
        s = self.f(s, self.tree[r - 1])
      if l & 1 :
        s = self.f(s, self.tree[l - 1])
        l += 1
      l >>= 1
      r >>= 1
    return s

INF = 1 << 60
ST = SegTree(N, -INF, max)

xs = [x for x, _ in XD]
for i in range(N - 1, -1, -1) :
  x, d = XD[i]
  j = bisect_left(xs, x + d)
  ST.update(i, max(i, ST.query(i, j)))

dp = [0] * (N + 1)
dp[N] = 1

for i in range(N) :
  dp[i] += dp[i - 1]
  dp[i] %= mod
  j = ST.query(i, i + 1)
  dp[j] += dp[i - 1]
  dp[j] %= mod

print(dp[N-1])

### FIXED CODE ###

from bisect import bisect_left
import sys
input = sys.stdin.readline

N = int(input())
XD = [[int(i) for i in input().split()] for _ in range(N)]

mod = 998244353

XD.sort()

class SegTree:
  def __init__(self, n, v, f) :
    i = 1
    while i < n : 
      i <<= 1
    self.n = i
    self.v = v
    self.f = f
    self.tree = [v] * (i << 1)

  def update(self, i, x) :
    i += self.n - 1
    self.tree[i] = x
    while i > 0 :
      i = (i - 1) // 2
      self.tree[i] = self.f(self.tree[i * 2 + 1], self.tree[i * 2 + 2])

  # [l, r)
  def query(self, l, r) :
    l = l + self.n
    r = r + self.n
    s = self.v
    while l < r :
      if r & 1 :
        r -= 1
        s = self.f(s, self.tree[r - 1])
      if l & 1 :
        s = self.f(s, self.tree[l - 1])
        l += 1
      l >>= 1
      r >>= 1
    return s

INF = 1 << 60
ST = SegTree(N, -INF, max)

xs = [x for x, _ in XD]
for i in range(N - 1, -1, -1) :
  x, d = XD[i]
  j = bisect_left(xs, x + d)
  ST.update(i, max(i, ST.query(i, j)))

dp = [0] * (N + 1)
dp[N] = 1

for i in range(N) :
  dp[i] += dp[i - 1]
  dp[i] %= mod
  j = ST.query(i, i + 1)
  dp[j] += dp[i - 1]
  dp[j] %= mod

print(dp[N-1])
### BUGGY CODE ###

n = int(input())
A=list(map(int, input().split()))
B=[A[i]+i+1 for i in range(n)]
C=[j+1-A[j] for j in range(n) if j+1-A[j]>0]
C2=set(C)

t=0
for i in range(n):
  if B[i] in C2:
    t+= C.count(B[i])
print(t)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
L = [i+x for i, x in enumerate(A)]
R = [i-x for i, x in enumerate(A) if i-x > 0]

from collections import Counter
P = Counter(L)
Q = Counter(R)
 
ans = 0
for k, v in P.items():
  if k in Q:
    ans += v*Q[k]
print(ans)
### BUGGY CODE ###

import sys
from fractions import gcd

X, Y = map(int, sys.stdin.readline().split())
R = 1

while True:
    R *= X
    if R >= 10**18:
        print(-1)
        break
    if R % Y != 0:
        print(R)
        break

### FIXED CODE ###

import sys

def main():
    X, Y = map(int, sys.stdin.readline().split())
    if X == Y:
        print(-1)
        return
    R = 1
    while True:
        R *= X
        if R >= 10**18:
            print(-1)
            return
        if R % Y != 0:
            print(R)
            return

main()
### BUGGY CODE ###

# 入力
data = input().split()
 
# プレイヤ人数
player = int(data[0])
# はじめのポイント
initPoint = int(data[1])
# 質問回数
question = int(data[2])
 
# はじめの各プレイヤのポイント
playerPoint = []
 
for i in range(player):
  playerPoint.append(initPoint)
 
# 問題解答
for i in range(question):
  # 全員のポイントを-1
  playerPoint = [i-1 for i in playerPoint]
  # 正解者
  corrPlayer = int(input())
  # 正解者のポイントを+1(減らさない)
  playerPoint[corrPlayer -1] = playerPoint[corrPlayer -1] + 1
  
# 解答
for i in range(player):
  if playerPoint[i] <= 0:
    print('No')
  else:
    print('Yes')

### FIXED CODE ###

# 入力
data = input().split()
 
# プレイヤ人数
player = int(data[0])
# はじめのポイント
initPoint = int(data[1])
# 質問回数
question = int(data[2])
 
# 正解しない場合のプレイヤのポイント
playerPoint = []
 
for i in range(player):
  playerPoint.append(initPoint - question)
 
# 問題解答
for i in range(question):
  # 正解者
  corrPlayer = int(input())
  # 正解者のポイントを+1(減らさない)
  playerPoint[corrPlayer -1] = playerPoint[corrPlayer -1] + 1
  
# 解答
for i in range(player):
  if playerPoint[i] <= 0:
    print('No')
  else:
    print('Yes')
### BUGGY CODE ###

from collections import Counter

# forを逆から回して下から素直にmodを取るとTLEだった
# 累積和的な計算で高速化、やりやすくするためにreverse
S = input()[::-1]
# ex. 1817181712114 → 4112171817181
# print(S)

# 0桁目までのMODを0とすることで、
# 1桁目を含む数が2019の倍数の時に都合が良くなる
X = [0]

# 4,14,114,2114,12114,...のmod2019を計算

for i, s in enumerate(S):
    X.append((X[-1] + int(s) * 10 ** i) % 2019)
# print(X)


C = Counter(X)
# print(C)

ans = 0
# Xが同じになったところを2つ選べば題意を満たす
# v_C_2の計算
for v in C.values():
    ans += v * (v - 1) // 2

print(ans)


### FIXED CODE ###

from collections import Counter

# forを逆から回して下から素直にmodを取るとTLEだった
# 累積和的な計算で高速化、やりやすくするためにreverse
S = input()[::-1]
# ex. 1817181712114 → 4112171817181
# print(S)

# 0桁目までのMODを0とすることで、
# 1桁目を含む数が2019の倍数の時に都合が良くなる
X = [0]

# 4,14,114,2114,12114,...のmod2019を計算

for i, s in enumerate(S):
    X.append((X[-1] + int(s) * pow(10, i, 2019)) % 2019)
# print(X)


C = Counter(X)
# print(C)

ans = 0
# Xが同じになったところを2つ選べば題意を満たす
# v_C_2の計算
for v in C.values():
    ans += v * (v - 1) // 2

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

from itertools import accumulate

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

# 初期位置を覚えておく
placeB = [0] * N
placeW = [0] * N

# 入力処理 & 初期位置処理
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    balls.append([c, a])
    if c == "B":
        placeB[a-1] = i
    else:
        placeW[a-1] = i


costB = [[0]*(2*N+1) for i in range(N+1)]  # i番目まででjより大きいB
costW = [[0]*(2*N+1) for i in range(N+1)]  # i番目まででjより大きいW

for i in range(N):
    for j in range(2*N):
        if balls[j][1] > i:
            if balls[j][0] == "B":
                costB[i][j+1] = 1
            else:
                costW[i][j+1] = 1

# 累積和
costB = [list(accumulate(cB)) for cB in costB]
costW = [list(accumulate(cW)) for cW in costW]

# dp
dp = [[float('inf')]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for b in range(N+1):
    for w in range(N+1):
        if b > 0:
            dp[b][w] = min(dp[b][w], dp[b-1][w] + costB[b][placeB[b-1]] + costW[w][placeB[b-1]])
        if w > 0:
            dp[b][w] = min(dp[b][w], dp[b][w-1] + costW[w][placeW[w-1]] + costB[b][placeW[w-1]])

print(dp[N][N])


### FIXED CODE ###

from itertools import accumulate

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

# 初期位置を覚えておく
placeB = [0] * N
placeW = [0] * N

# 入力処理 & 初期位置処理
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    balls.append([c, a])
    if c == "B":
        placeB[a-1] = i
    else:
        placeW[a-1] = i


costB = [[0]*(2*N+1) for i in range(N+1)]  # i番目まででjより大きいB
costW = [[0]*(2*N+1) for i in range(N+1)]  # i番目まででjより大きいW

for i in range(N):
    for j in range(2*N):
        if balls[j][1] > i:
            if balls[j][0] == "B":
                costB[i][j+1] = 1
            else:
                costW[i][j+1] = 1

# 累積和
costB = [list(accumulate(cB)) for cB in costB]
costW = [list(accumulate(cW)) for cW in costW]

# dp
dp = [[float('inf')]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for b in range(N+1):
    for w in range(N+1):
        if b > 0:
            dp[b][w] = min(dp[b][w], dp[b-1][w] + costB[b][placeB[b-1]] + costW[w][placeB[b-1]])
        if w > 0:
            dp[b][w] = min(dp[b][w], dp[b][w-1] + costW[w][placeW[w-1]] + costB[b][placeW[w-1]])

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

import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

n,q = read_int()
S = read_str()
lr = [read_int() for _ in range(q)]


def solve():
    for i in range(q):
        l,r = lr[i]
        res = 0
        for j in range(l,r):
            # print(S[j-1:j +1])
            if S[j - 1: j + 1] == 'AC':
                res += 1
        print(res)


if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

n,q = read_int()
S = read_str()
lr = [read_int() for _ in range(q)]

dp = [0 for i in range(n+1)]
def solve():
    for i in range(1, n):
        dp[i+1] = dp[i]
        if S[i - 1:i + 1] == 'AC':
            dp[i +1] += 1

    for i in range(q):
        l,r = lr[i]
        print(dp[r]-dp[l])

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

def get_min_p(offset, length, k, arr):
  if k == 1: return sum(arr[offset:offset + length])
  if k == 2:
    min_diff = float('inf')
    p = 0
    for i in range(1, length):
      a = sum(arr[offset:offset + i])
      b = sum(arr[offset + i:])
      if abs(a - b) < min_diff:
        min_diff = abs(a - b)
        p = max(a, b)
      #print("arr:{}, i:{}, p:{}".format(
      #  arr[offset:offset + length], i, p))
    return p
  else:
    e = len(arr) - k + 2
    p = [float('inf')] * e
    for i in range(1, e):
      #print("p:{}, i:{}".format(p, i))
      a = get_min_p(offset + i, length - i, k - 1, arr)
      b = sum(arr[offset:offset + i])
      p[i] = max(a, b)
    return min(p)

n, k = map(int, input().split())
a = [int(input()) for i in range(n)]

print(get_min_p(0, n, k, a))

### FIXED CODE ###

def check(p, k, arr):
  subtotal = 0
  num_of_tracks = 1
  for a in arr:
    subtotal += a
    if subtotal > p:
      num_of_tracks += 1
      if num_of_tracks > k: return False
      subtotal = a
  return True

n, k = map(int, input().split())
arr = [int(input()) for i in range(n)]

min_p = max(arr)
max_p = sum(arr)
while min_p < max_p:
  mid_p = (min_p + max_p) // 2
  if check(mid_p, k, arr):
    max_p = mid_p
  else:
    min_p = mid_p + 1

print(min_p)
### BUGGY CODE ###

n = int(input())
ans = 0

for i in range(1, n+1):
    for j in range(1, n // i + 1):
        ans += i * j
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0

for i in range(1, n + 1):
    y = n // i
    ans += y * (y+1) * i // 2
print(ans)
### BUGGY CODE ###

n=int(input())
ans=0
for i in range(n):
   ans+=i
print(ans)

### FIXED CODE ###

n=int(input())

print(((n-1)*(n))//2)
### BUGGY CODE ###

n=int(input())
nums=input().rstrip().split(" ")
#print(nums)
count=0
for num in nums:
    if num!="1":
        count+=1
if count==n:
    print("-1")
i=1
while nums!=[]:
    for j in range(len(nums)):
        if int(nums[j])!=i:
            nums[j]="0"
            #print(nums)
        else:
            nums=[i for i in nums if i!="0"]
            if nums.count(str(i))>=1:
                nums.remove(str(i))
                i=i+1
                #print(nums)
                #print(i)
            break
        
'''nums=[i for i in nums if i!="0"]
if nums.count(str(i))>=1: nums.remove(str(i))
    i=i+1'''
#print(nums)
#print(i)
ans=n-i+1
print(ans)

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    k = 1
    for i in range(n):
        if a[i] == k:
            k += 1
    k -= 1
    print(n - k) if k else print(-1)

main()
### BUGGY CODE ###

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

dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if vw[i][0]>j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-vw[i][0]]+vw[i][1])
            #[print(*dp[l]) for l in range(n+1)]
            #print("---------------")            
print(dp[n][w])

### FIXED CODE ###

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

dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if vw[i][0]>j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-vw[i][0]]+vw[i][1])
            #[print(*dp[l]) for l in range(n+1)]
            #print("---------------")            
print(dp[n][w])
### BUGGY CODE ###

from collections import defaultdict
def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(set)
    block = defaultdict(set)
    group = defaultdict(set)
    cand = defaultdict(set)
    uft = defaultdict(int)
    for i in range(m):
        a, b = map(int, input().split())
        friend[a].add(b)
        friend[b].add(a)
    for j in range(k):
        c, d = map(int, input().split())
        block[c].add(d)
        block[d].add(c)
    for i in range(1, n+1):
        if uft[i] != 0:
            group[i] = group[uft[i]]
        else:
            group[i] = set()
            q = [i]
            while q:
                p = q.pop()
                if p in group[i]:
                    continue
                q += list(friend[p])
                group[i].add(p)
            for j in group[i]:
                uft[j] = i
        cand[i] = group[i] - friend[i] - block[i]
    return ' '.join(str(len(cand[i])-1) for i in range(1, n+1))

print(answer())

### FIXED CODE ###

from collections import defaultdict, Counter
import sys

def root(uft, x):
    if uft[x] == x: return x
    uft[x] = root(uft, uft[x])
    return uft[x]

def union(uft, rank, x, y):
    x = root(uft, x)
    y = root(uft, y)
    if x == y:
        return

    if rank[x] >= rank[y]:
        uft[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
    else:
        uft[x] = y

def same(uft, x, y):
    return root(uft, x) == root(uft, y)

def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(int)
    block = defaultdict(int)
    group = defaultdict(set)
    uft = [i for i in range(n+1)]
    rank = [0] * (n+1)
    for i in range(m):
        a, b = map(int, input().split())
        union(uft, rank, a, b)
        friend[a] += 1
        friend[b] += 1
    for j in range(k):
        c, d = map(int, input().split())
        if not same(uft, c, d):
            continue
        block[c] += 1
        block[d] += 1
    for i in range(1, n+1):
        root(uft, i)
    c = Counter(uft)
    return [c[uft[i]]-block[i]-friend[i]-1 for i in range(1, n+1)]

print(*answer())
### BUGGY CODE ###

import itertools

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

def tri_d(a,b,c):
  if (a+b>c) and (b+c>a) and (c+a>b):
    return True
  else:
    return False


ans=0
C=list(itertools.combinations(L, 3))
for c in C:
  if tri_d(c[0], c[1], c[2]):
        ans+=1
print(ans)

### FIXED CODE ###

import bisect

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

count=0
for i in range(N-2):
  a=L[i]
  for j in range(i+1, N-1):
    b=L[j]
    r=bisect.bisect_left(L, a+b)
    count+=r-1-j
    
print(count)