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

import sys
n, m = map(int, input().split())

As = []
a_ = -1
for i in range(m):
  a = int(input())
  if a == a_ + 1:
    print(0)
    sys.exit()
  As.append(a)
  a_ = a

nums = [1]
if 1 in As:
  nums.append(0)
else:
  nums.append(1)
  
for i in range(2, n + 1):
  if i in As:
    nums.append(0)
  else:
    nums.append((nums[i-1] + nums[i-2]) % 1000000007)
    
print(nums[-1])

### FIXED CODE ###

import sys
n, m = map(int, input().split())

if m > 0:
  As = set(map(int, sys.stdin))
else:
  As = set()

nums = [0] * (n + 1)
nums[0] = 1
if 1 in As:
  pass
else:
  nums[1] = 1
  
for i in range(2, n + 1):
  if i in As:
    continue
  else:
    nums[i] = (nums[i-1] + nums[i-2]) % 1000000007
    
print(nums[-1])
### BUGGY CODE ###

N, K = map(int, input().split())
for i in range(10**8):
    if N > K** i and N < K**(i+1):
        print(i+1)
        break


### FIXED CODE ###

N, K = map(int, input().split())
i = N/K
cnt = 1
while i >= 1:
    i = i/K
    cnt += 1
print(cnt)
### BUGGY CODE ###

import math

N = int(input())
LI = []
for a in range(N):
    LI.append(int(input()))

MOD = 998244353
SUM = sum(LI)

# dp[t][r]: t までの整数を塗り分けたときに赤にしたやつの和が r となる場合の数
dp = [[0 for _ in range(SUM + 1)] for _ in range(len(LI))]
dp[0][0] = 2  # 緑か青
dp[0][LI[0]] = 1
for t in range(1, len(LI)):
    for r in range(len(dp[t])):
        dp[t][r] += dp[t - 1][r] * 2 % MOD
        dp[t][r] += dp[t - 1][r - LI[t]] % MOD if 0 <= r - LI[t] <= len(dp[t - 1]) else 0

# 選び方の組み合わせ数
ans = (3 ** len(LI)) % MOD
# 赤の合計が SUM / 2 以上だと三角形作れないので、選び方の合計から引く
# 緑と青が一番大きいケースも同じなので * 3
ans -= sum([dp[-1][r] for r in range(math.ceil(SUM / 2), SUM + 1)]) * 3
ans %= MOD

if SUM % 2 == 0:
    # r == g, b == 0 のケースを重複して引いてるので足したい
    # dp[t][r]: t までの整数を赤と青だけで塗り分けたときに赤にしたやつの和が r となる場合の数
    dp = [[0 for _ in range(SUM // 2 + 1)] for _ in range(len(LI))]
    dp[0][0] = 1  # 青
    dp[0][LI[0]] = 1
    for t in range(1, len(LI)):
        for r in range(len(dp[t])):
            dp[t][r] += dp[t - 1][r] % MOD
            dp[t][r] += dp[t - 1][r - LI[t]] % MOD if 0 <= r - LI[t] <= len(dp[t - 1]) else 0
    # 赤緑、赤青、緑青
    ans += dp[-1][SUM // 2] * 3
    ans %= MOD

print(ans)


### FIXED CODE ###

import math

N = int(input())
LI = []
for a in range(N):
    LI.append(int(input()))

MOD = 998244353
SUM = sum(LI)

# dp[t][r]: t までの整数を塗り分けたときに赤にしたやつの和が r となる場合の数
dp = [[0 for _ in range(SUM + 1)] for _ in range(len(LI))]
dp[0][0] = 2  # 緑か青
dp[0][LI[0]] = 1
for t in range(1, len(LI)):
    for r in range(len(dp[t])):
        dp[t][r] += dp[t - 1][r] * 2 % MOD
        dp[t][r] += dp[t - 1][r - LI[t]] % MOD if 0 <= r - LI[t] <= len(dp[t - 1]) else 0

# 選び方の組み合わせ数
ans = (3 ** len(LI)) % MOD
# 赤の合計が SUM / 2 以上だと三角形作れないので、選び方の合計から引く
# 緑と青が一番大きいケースも同じなので * 3
ans -= sum([dp[-1][r] for r in range(math.ceil(SUM / 2), SUM + 1)]) * 3
ans %= MOD

if SUM % 2 == 0:
    # r == g, b == 0 のケースを重複して引いてるので足したい
    # dp[t][r]: t までの整数を赤と青だけで塗り分けたときに赤にしたやつの和が r となる場合の数
    dp = [[0 for _ in range(SUM // 2 + 1)] for _ in range(len(LI))]
    dp[0][0] = 1  # 青
    dp[0][LI[0]] = 1
    for t in range(1, len(LI)):
        for r in range(len(dp[t])):
            dp[t][r] += dp[t - 1][r] % MOD
            dp[t][r] += dp[t - 1][r - LI[t]] % MOD if 0 <= r - LI[t] <= len(dp[t - 1]) else 0
    # 赤緑、赤青、緑青
    ans += dp[-1][SUM // 2] * 3
    ans %= MOD

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

from collections import Counter

N = int(input())
S = input()

tmp = N
for i in range(N):
    count_E = Counter(S[: i])['W']
    count_W = Counter(S[i + 1:])['E']
    if count_E + count_W < tmp:
        tmp = count_E + count_W
print(tmp)

### FIXED CODE ###

from collections import Counter

N = int(input())
S = input()

count_E = Counter(S)['E']
count_W = Counter(S)['W']

right = 0
left = count_E
tmp = N
for i in range(N):
    if S[i] == 'E':
        left -= 1
    if right + left < tmp:
        tmp = right + left
    if S[i] == 'W':
        right += 1
print(tmp)
### BUGGY CODE ###

sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx,sy,0)]
for i in range(n):
    data.append(tuple(map(int,input().split())))
data.append((gx,gy,0))
for i in range(n+2):
    for j in range(i,n+2):
        if i==j:
            g[i].append((0,j))
            g[j].append((0,i))
            continue
        tmp=max(0,((data[i][0]-data[j][0])*(data[i][0]-data[j][0])+(data[i][1]-data[j][1])*(data[i][1]-data[j][1]))**0.5-data[i][2]-data[j][2])
        g[i].append((tmp,j))
        g[j].append((tmp,i))

def dijkstra(g,st,ed):
    from heapq import heappush, heappop, heapify
    inf=10**10+1
    dist=[inf for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st))
    while que:
        c,v=heappop(que)
        if dist[v]<c:
            continue
        for i in range(len(g[v])):
            if g[v][i][0]+c<dist[g[v][i][1]]:
                dist[g[v][i][1]]=g[v][i][0]+c
                heappush(que,(g[v][i][0]+c,g[v][i][1]))
    return dist[ed]

print(dijkstra(g,0,n+1))

### FIXED CODE ###

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])
### BUGGY CODE ###

H,W = map(int,input().split()) 
A = [[0]*W for _ in range(H)]
M = 0
queue = []
for i in range(H):
  s = input()
  for j in range(W):
    if s[j]== '#':
      queue.append([i,j,0])
      A[i][j] = '#'
while queue:
  i,j,cost = queue.pop(0)
  M=max(M,cost)
  if i+1 < H and A[i+1][j] != '#':
    queue.append([i+1,j,cost+1])
    A[i+1][j] = '#'
  if i-1 >= 0 and A[i-1][j] != '#':
    queue.append([i-1,j,cost+1])
    A[i-1][j] = '#'
  if j+1 < W and A[i][j+1] != '#':
    queue.append([i,j+1,cost+1])
    A[i][j+1] = '#'
  if j-1 >= 0 and A[i][j-1] != '#':
    queue.append([i,j-1,cost+1])
    A[i][j-1] = '#'
print(M)
    

### FIXED CODE ###

from collections import deque

H,W = map(int,input().split()) 
A = [[0]*W for _ in range(H)]
M = 0
queue = deque()
for i in range(H):
  s = input()
  for j in range(W):
    if s[j]== '#':
      queue.append([i,j,0])
      A[i][j] = '#'
while queue:
  i,j,cost = queue.popleft()
  M=max(M,cost)
  if i+1 < H and A[i+1][j] != '#':
    queue.append([i+1,j,cost+1])
    A[i+1][j] = '#'
  if i-1 >= 0 and A[i-1][j] != '#':
    queue.append([i-1,j,cost+1])
    A[i-1][j] = '#'
  if j+1 < W and A[i][j+1] != '#':
    queue.append([i,j+1,cost+1])
    A[i][j+1] = '#'
  if j-1 >= 0 and A[i][j-1] != '#':
    queue.append([i,j-1,cost+1])
    A[i][j-1] = '#'
print(M)
### BUGGY CODE ###

from collections import defaultdict
n=int(input())
a = list(map(int, input().split()))
memo = defaultdict(int)
x = []
for y in a:
    i = y
    xx = defaultdict(int)
    c = 0
    while i%2==0:
        c += 1
        i //= 2
    memo[2] = max(memo[2], c)
    xx[2]=c
    for j in range(3, int(i**.5)+2, 2):
        c=0
        while i%j==0:
            c += 1
            i //= j
        memo[j] = max(memo[j], c)
        xx[j] = c
    if i!=1:
        xx[i]=1
        memo[i] = max(memo[i], 1)
    x.append(xx)
mod = 10**9+7
result = 0
for i in range(n):
    num = 1
    for s, t in memo.items():
        num *= pow(s, t-x[i][s])
    result = (result+num)%mod

print(result)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

mod = 10**9 + 7
memo = defaultdict(int)
base = 0
for i in a:
    base = (base+pow(i, mod-2, mod))%mod
    num = i
    for j in range(2, int(i**.5)+1):
        if num%j==0:
            c = 0
            while num%j==0:
                num //= j
                c += 1
            memo[j] = max(memo[j], c)
    if num != 1:
        memo[num] = max(memo[num], 1)
k = 1
for s, t in memo.items():
    k = (k*pow(s, t, mod))%mod

print((k*base)%mod)
### BUGGY CODE ###

n,q=map(int,input().split())
event=[]
for _ in range(n):
  s,t,x=map(int,input().split())
  event.append([s-x,1,x])
  event.append([t-x,-1,x])
event=sorted(event,key=lambda x:x[0])
event.append([10**10,1,10**10])
pos=[int(input()) for _ in range(q)]
sx=set()
cnt=0
m=10**10
ans=[]
for p in pos:
  while event[cnt][0]<=p:
    s,f,x=event[cnt]
    cnt+=1
    if f==1:
      sx.add(x)
      m=min(m,x)
    else:
      sx.remove(x)
      if m==x:
        if len(sx)==0:
          m=10**10
        else:
          m=min(list(sx))
  if len(sx)==0:
    ans.append(-1)
  else:
    ans.append(m)
for i in ans:
  print(i)

### FIXED CODE ###

from bisect import bisect_left

n,q=map(int,input().split())
work=[list(map(int,input().split())) for _ in range(n)]
work=sorted(work,key=lambda x:x[2])
pos=[int(input()) for _ in range(q)]
ans=[-1]*q
checked=[-1]*q
for s,t,x in work:
  l=bisect_left(pos,s-x)
  r=bisect_left(pos,t-x)
  while l<r:
    if checked[l]==-1:
      checked[l]=r
      ans[l]=x
      l+=1
    else:
      l=checked[l]
for i in ans:
  print(i)
### BUGGY CODE ###

from sys import exit, stdin

S = list(stdin.readline().rstrip())
ans = [0 for _ in S]

for i, s in enumerate(S):
    flag = True
    if s == 'R':
        index = i
        while flag:
            index += 1
            if S[index] == 'L':
                if (index - i) % 2 == 1:
                    ans[index-1] += 1
                else:
                    ans[index] += 1
                flag = False
for i, s in enumerate(S):
    flag = True
    if s == 'L':
        index = i
        while flag:
            index -= 1
            if S[index] == 'R':
                if (i - index) % 2 == 1:
                    ans[index+1] += 1
                else:
                    ans[index] += 1
                flag = False
print(*ans)

### FIXED CODE ###

from sys import exit, stdin

S = list(stdin.readline().rstrip())
ls = len(S)

candidates = []
for i in range(ls-1):
    if S[i] == 'R' and S[i+1] == 'L':
        candidates.append(i)
lc = len(candidates)

ans = [0 for _ in S]

for i in range(lc):
    l_index, r_index = candidates[i], candidates[i]+1

    while l_index > 0 and S[l_index - 1] == 'R':
        l_index -= 1
    while r_index + 1 < ls and S[r_index + 1] == 'L':
        r_index += 1

    even, odd = 0, 0
    idx = candidates[i]

    for j in range(l_index, idx):
        if (idx-j) % 2 == 0:
            even += 1
        else:
            odd += 1
    for j in range(idx, r_index+1):
        if (j-idx) % 2 == 0:
            even += 1
        else:
            odd += 1
    
    ans[idx] += even
    ans[idx+1] += odd

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

from bisect import bisect

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

for i in range(m):
    an.sort()
    b,c=map(int,input().split())
    cnt = bisect(an,c)
    if b <= cnt:
        for j in range(b):
            an[j]=c
    else:
        for j in range(cnt):
            an[j]=c
print(sum(an))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
D = []
for i in range(M):
    b, c = map(int, input().split())
    D.append((b, c))
A = sorted(A)
D = sorted(D, key=lambda x: x[1], reverse=True)

i = 0
for j in range(M):
    p, q = D[j]
    while p > 0:
        if i < N and q > A[i]:
            A[i] = q
            i += 1
        else:
            break
        p -= 1
print(sum(A))
### BUGGY CODE ###

L,R= map(int,input().split())
#境界条件
bool = True
l = L % 2019
r = R % 2019
if l == 0 or r == 0:
    ans = 0
else:
    r+=2019
    for i in range(L,R):
        for j in range(i+1,R+1):
            temp = (i * j) % 2019
            if bool:
                min = temp
                ans = min
                bool = False
            elif min > temp:
                min = temp
                ans = min
print(ans)

### FIXED CODE ###

L,R= map(int,input().split())
#境界条件
bool = True
flag = False
for i in range(L,R):
    for j in range(i+1,R+1):
        temp = (i * j) % 2019
        if bool:
            min = temp
            ans = min
            bool = False
        elif min > temp:
            min = temp
            ans = min
        if min == 0:
            flag = True
            break
    if flag:
        break
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

# kitaichi_p_list = [(p + 1)/2 for p in p_list]

max_sum = 0
for i in range(N):
    tmp_sum = sum(p_list[i:i+K])
    if(max_sum < tmp_sum):
        max_sum = tmp_sum
        ichi = i

kitaichi = [(p+1)/2 for p in p_list[ichi:ichi+K]]

print(sum(kitaichi))

### FIXED CODE ###

from sys import stdin

def main():

    input = stdin.readline

    N,K = map(int,input().split())
    p_list = [(p+1)/2 for p in list(map(int,input().split()))]

    # Sを計算
    S = [0]
    for p in p_list:
        S.append(S[-1] + p)
        # print(S)

    # i:i+kを計算

    maxs = 0
    for i in range(N-K+1):
        p_num = S[i+K] - S[i]
        if(maxs < p_num):
            maxs = p_num
    
    print(maxs)

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

import sys
sys.setrecursionlimit(10**9)

N,Q = map(int,input().split())
node = [[]for i in range(0,N+1,1)]
for i in range(0,N-1,1):
    a,b = map(int,input().split())
    node[a].append(b)
    node[b].append(a)
node_score = [0]*(N+1)#スコア
for i in range(0,Q,1):
    p,x = map(int,input().split())
    node_score[p] += x

ans = [0]*(N+1)
def bfs(n,preN):
    ans[n] = ans[preN]+node_score[n]
    for to in node[n]:
        if to != preN:
            bfs(to,n)
bfs(1,0)
print(" ".join(list(map(str,ans[1:N+1]))))

### FIXED CODE ###

from collections import deque 
#スタック
s = deque([])

N,Q = map(int,input().split())
node = [[]for i in range(0,N+1,1)]
for i in range(0,N-1,1):
    a,b = map(int,input().split())
    node[a].append(b)
    node[b].append(a)
node_score = [0]*(N+1)#スコア
for i in range(0,Q,1):
    p,x = map(int,input().split())
    node_score[p] += x

ans = [0]*(N+1)

s.append([1,0])
while len(s) > 0:
    n,preN = s.pop()
    ans[n] = ans[preN]+node_score[n]
    for to in node[n]:
        if to != preN:
            s.append([to,n])

print(" ".join(list(map(str,ans[1:N+1]))))
### BUGGY CODE ###

from itertools import accumulate, islice
from bisect import bisect_left

n = int(input())
xs = [int(x) for x in input().split()]
ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]

rs = range(2, n-2)
v = []
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    splits = ((zs[j+k], z - zs[j+k]) for k in (-1, 0, 1) if 0 <= j+k <= i)
    a, b = min(splits, key=lambda s:abs(s[0]-s[1]))

    j = bisect_left(zs, (total - z)/2 + z)
    splits = (sorted((zs[j+k] - z, total - zs[j+k])) for k in (-1, 0, 1) if i <= j+k <= n-2)
    c, d = min(splits, key=lambda s:abs(s[0]-s[1]))

    minn, _, _, maxx = sorted((a,b,c,d))
    v.append(maxx - minn)

print(min(v) if v else max(xs) - min(xs))

### FIXED CODE ###

from itertools import accumulate, islice
from bisect import bisect_left

n = int(input())
xs = [int(x) for x in input().split()]
ys = list(accumulate(xs))
zs, total = ys[:-1], ys[-1]

rs = range(2, n-2)
v = []
for i, z in islice(enumerate(zs), 1, n-1):
    j = bisect_left(zs, z//2)
    splits = ((zs[j+k], z - zs[j+k]) for k in (-1, 0, 1) if 0 <= j+k <= i)
    a, b = min(splits, key=lambda s:abs(s[0]-s[1]))

    j = bisect_left(zs, (total - z)//2 + z)
    splits = ((zs[j+k] - z, total - zs[j+k]) for k in (-1, 0, 1) if i <= j+k <= n-2)
    c, d = min(splits, key=lambda s:abs(s[0]-s[1]))

    minn, _, _, maxx = sorted((a,b,c,d))
    v.append(maxx - minn)

print(min(v) if v else max(xs) - min(xs))
### BUGGY CODE ###

N=int(input())
p=1
for i in range(N):
  p*=(i+1)
#  p=p%(10**9+7)

p=p%(10**9+7)
print(p)

### FIXED CODE ###

N=int(input())
p=1
for i in range(N):
  p*=(i+1)
  p=p%(10**9+7)
print(p)
### BUGGY CODE ###

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

import fractions
import copy
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

ans = 1
temp_A = A
for i in range(N):
    temp_A = copy.deepcopy(A)
    del temp_A[i]
    ans = max(ans, gcd_list(temp_A))

print(ans)

### FIXED CODE ###

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

import fractions
import copy
from functools import reduce

#最大公約数を求める関数
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

l = []
sorted_A = sorted(A)
ind = 0
for i in range(1, len(A)):
    if gcd_list([sorted_A[0], sorted_A[i]]) == 1:
        ind = i
        break
if ind == 0:
    ind = 1
for i in [0,ind]:
    sorted_A = sorted(A)
    del sorted_A[i]
    l.append(gcd_list(sorted_A))

print(max(l))
### BUGGY CODE ###

N = int(input())
Alist = [int(x) for x in input().split()]
invans = 0
for i in range(N):
    for j in range(N):
        if i == j or Alist[i] < Alist[j]:
            None
        else:
            if Alist[i] % Alist[j] == 0:
                invans += 1
                break

print(N - invans)

### FIXED CODE ###

N = int(input())
Alist = [int(x) for x in input().split()]
M = max(Alist)
A0 = ['NotUse']
Abool = A0 + [0 for x in range(M)]
Alist.sort()
ans = 0

for i in Alist:
    for j in range(i,M+1,i):
        if Abool[j] >= 2:
            None
        else:
            Abool[j] += 1
    
for i in Alist:
    if Abool[i] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = []
count = 0
for _ in range(N):
  item = input()
  if (item in A) == False:
    count = count + 1
  A.append(item)
print(count)


### FIXED CODE ###

N = int(input())
A = set([])
count = 0
for _ in range(N):
  item = input()
  if (item in A) == False:
    count = count + 1
    A.add(item)
print(count)
### BUGGY CODE ###

n, k = map(int, input().split())
array = list(map(int, input().split()))
from collections import Counter
lis = sorted((Counter(array)).items(), key = lambda x: x[1])
count = 0
while len(lis) > k:
    count += lis[0][1]
    lis.remove(lis[0])
print(count)

### FIXED CODE ###

import collections
n, k = map(int, input().split())
d = collections.defaultdict(int)
b = map(int, input().split())
for e in b:
    d[e] += 1
ret = 0
a = sorted([v for v in d.values()], reverse = True)
while len(a) > k:
    ret  += a.pop()
print(ret)
### BUGGY CODE ###

from collections import defaultdict
n, m = list(map(int, input().split()))
d1 = defaultdict(set)
for i in range(m):
  u, v = list(map(int, input().split()))
  d1[u].add(v)
s, t = list(map(int, input().split()))
d2 = defaultdict(set)

def dfs (x, nx, cnt, visited):
  if nx in visited:
    return
  if cnt==3:
    d2[x].add(nx)
  elif cnt>3:
    return

  for nnx in d1[nx]:
    dfs(x, nnx, cnt+1, visited)
  visited.add(nx)

for i in range(1, n+1):
  visited = set()
  dfs(i, i, 0, visited)
  visited.add(i)

from heapq import heappop, heappush
prev = [-1 for _ in range(n+1)]
def dijkstra(s, graph):
  d = [float("INF") for _ in range(n+1)]
  d[s] = 0
  q = []
  heappush(q, [0, s])

  while q:
    dt, v = heappop(q)
    if d[v] < dt:
      continue
    for to in graph[v]:
      if d[to] > dt+1:
        d[to] = dt+1
        prev[to] = v
        heappush(q, [d[to], to])
  return d
dd = dijkstra(s, d2)
if dd[t]==float("INF"):
  print(-1)
else:
  print(dd[t])

### FIXED CODE ###

from collections import defaultdict, deque
n, m = list(map(int, input().split()))
graph = defaultdict(list)
for i in range(m):
  u, v = list(map(int, input().split()))
  graph[u].append(v+n)
  graph[u+n].append(v+2*n)
  graph[u+2*n].append(v)
s, t = list(map(int, input().split()))
dist = [-1 for i in range(3*n+10)]

def bfs():
  que = deque([s])
  dist[s] = 0
  while len(que) > 0:
    cur = que.popleft()
    for to in graph[cur]:
      if dist[to] == -1:
        dist[to] = dist[cur]+1
        que.append(to)

bfs()
print(dist[t]//3)
### BUGGY CODE ###

def main():
  import sys
  input=sys.stdin.buffer.readline
  n=int(input())+1
  data=[set()for _ in range(2*n)]
  def update(i,x):
    i+=n
    data[i]={x}
    i//=2
    while i:
      data[i]=data[i*2]|data[i*2+1]
      i//=2
  def query(l,r):
    l+=n
    r+=n
    s=set()
    while l<r:
      if l&1:
        s|=data[l]
        l+=1
      if r&1:
        r-=1
        s|=data[r]
      l//=2
      r//=2
    return len(s)
  for i,c in enumerate(input()[:-1]):update(i,c)
  for _ in range(int(input())):
    q,a,b=input().split()
    if q[0]>49:print(query(int(a)-1,int(b)))
    else:update(int(a)-1,b[0])
main()

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
n=int(input())+1
data=[0]*n*2
def update(i,x):
  i+=n
  data[i]=x
  i//=2
  while i:
    data[i]=data[i*2]|data[i*2+1]
    i//=2
def query(l,r):
  l+=n
  r+=n
  s=0
  while l<r:
    if l&1:
      s|=data[l]
      l+=1
    if r&1:
      r-=1
      s|=data[r]
    l//=2
    r//=2
  return sum(map(int,bin(s)[2:]))
for i,c in enumerate(input()[:-1]):
  update(i,2**(c-97))
for _ in range(int(input())):
  q,a,b=input().split()
  if q[0]>49:print(query(int(a)-1,int(b)))
  else:update(int(a)-1,2**(b[0]-97))
### BUGGY CODE ###

K,S=map(int,input().split())
ans=0
for z in range(0,K+1):
  for y in range(0,z+1):
    for x in range(0,y+1):
      if x+y+z==S:
        if x==y==z:
          ans+=1
        elif x!=y!=z:
          ans+=6
        else:
          ans+=3
print(ans)



### FIXED CODE ###

K,S=map(int,input().split())
ans=0
for x in range(K+1):
  for y in range(K+1):
    if 0<=S-x-y<=K:
      ans+=1
print(ans)
### BUGGY CODE ###


#<134>
N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
#print(A)
for n in range(N):
    x = A[n]
    A[n] = 0
    print(max(A))
    A[n] = x
    #print(A)

### FIXED CODE ###

N = int(input())
A = []
for n in range(N):
    A.append(int(input()))

B = sorted(A, reverse = True)
max1 = B[0]
max2 = B[1]
for a in A:
    print(max2 if a == max1 else max1)
### BUGGY CODE ###

N=int(input())
flag=True
inList=list(map(int,input().split()))
List=[]
for a in inList:
    for numbers in List:
        if numbers==a:
            print('NO')
            flag=False
            break
    if flag:
        List.append(a)
    else:
        break

if flag:
    print('YES')

### FIXED CODE ###

from collections import Counter
N=int(input())
flag=True
inList=list(map(int,input().split()))

c=Counter(inList)
cv=list(c.values())
for i in cv:
    if i!=1:
        print('NO')
        flag=False
        break
if flag:
    print('YES')
### BUGGY CODE ###

N=int(input())
d=[int(x) for x in input().split()]
d.sort()
M=max(d)
A=[]
for i in range(M+1):
  A.append(len([j for j in range(N) if d[j]==i]))
count=0
c=0
while(count<N/2):
  count=count+A[c]
  c=c+1
if count!=N/2:
  print(0)
elif count==N/2:
  d=0
  while(count==N/2):
    count=count+A[c]
    c=c+1
    d=d+1
  print(d)

### FIXED CODE ###

N=int(input())
d=[int(x) for x in input().split()]
d.sort()
print(d[int(N/2)]-d[int(N/2)-1])
### BUGGY CODE ###

import collections
from operator import mul
from functools import reduce
mod = 10**9 + 7
def cmb(n,r):
    p,q = 1,1
    for i in range(r):
        p = p*(n-i)%mod
        q = q*(i+1)%mod
    return p * pow(q,mod-2,mod) % mod

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

for k in range(N):
  A[k] -= (10**6)
  C = collections.Counter(A)
  A[k] += (10**6)
  values, counts = zip(*C.most_common())
  ans = 0
  for i in range(len(counts)):
    if counts[i] == 1:
      pass
    else:
      ans += cmb(counts[i],2)
  print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
B = Counter(A)
ans = 0

for i in B.values():
  ans += i*(i-1)//2
for a in A:
  k = B[a]
  print(ans - (k*(k-1)//2)+((k-1)*(k-2)//2))