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

import sys
sys.setrecursionlimit(2000000000)
input=lambda : sys.stdin.readline().rstrip('\n')

n,q=map(int,input().split())
s=input()
dic=[[0 for i in range(q)] for i in range(26)]
for i in range(q):
    t,d=input().split()
    c=ord(t)-ord('A')
    if d=='L':
        dic[c][i]=-1
    if d=='R':
        dic[c][i]=1

l,r=-1,n
while l+1<r:
    mid=(l+r)//2
    d=mid
    f=False
    for i in range(q+1):
        if d==-1:
            f=True
            break
        if d==n or i==q:
            f=False
            break
        c=ord(s[d])-ord('A')
        if dic[c][i]!=0:
            d+=dic[c][i]
    if f:
        l=mid
    else:
        r=mid
tmp1=l
l,r=-1,n
while l+1<r:
    mid=(l+r)//2
    d=mid
    f=False
    for i in range(q+1):
        if d==n:
            f=True
            break
        if d==-1 or i==q:
            f=False
            break
        c=ord(s[d])-ord('A')
        if dic[c][i]!=0:
            d+=dic[c][i]
    if f:
        r=mid
    else:
        l=mid
print(max(r-tmp1-1,0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(2000000000)
input=lambda : sys.stdin.readline().rstrip('\n')

n,q=map(int,input().split())
s=input()
dic=[[0 for i in range(q)] for i in range(26)]
for i in range(q):
    t,d=input().split()
    c=ord(t)-ord('A')
    if d=='L':
        dic[c][i]=-1
    if d=='R':
        dic[c][i]=1

l,r=-1,n
while l+1<r:
    mid=(l+r)//2
    d=mid
    f=False
    for i in range(q+1):
        if d==-1:
            f=True
            break
        if d==n or i==q:
            f=False
            break
        c=ord(s[d])-ord('A')
        if dic[c][i]!=0:
            d+=dic[c][i]
    if f:
        l=mid
    else:
        r=mid
tmp1=l
l,r=-1,n
while l+1<r:
    mid=(l+r)//2
    d=mid
    f=False
    for i in range(q+1):
        if d==n:
            f=True
            break
        if d==-1 or i==q:
            f=False
            break
        c=ord(s[d])-ord('A')
        if dic[c][i]!=0:
            d+=dic[c][i]
    if f:
        r=mid
    else:
        l=mid
print(max(r-tmp1-1,0))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
# 幅優先探索（行きがけ）
import collections
import sys
import copy
import re
import math
import itertools


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    H, W, M = LI()

    HList = [0]*H
    WList = [0]*W
    graph = [[0 for _ in range(W)] for _ in range(H)]

    for m in range(M):
        h, w = LI()
        HList[h-1] += 1
        WList[w-1] += 1
        graph[h-1][w-1] += 1

    Hmax = max(HList)
    Wmax = max(WList)

    HIndex = [i for i, v in enumerate(HList) if v == Hmax]
    WIndex = [i for i, v in enumerate(WList) if v == Wmax]

    ans = Hmax + Wmax
    for h in HIndex:
        for w in WIndex:
            if graph[h][w] == 0:
                print(ans)
                return

    print(ans-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding: utf-8
# Your code here!
# 幅優先探索（行きがけ）
import collections
import sys
import copy
import re
import math
import itertools


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    H, W, M = LI()

    HList = [0]*H
    WList = [0]*W
    graph = set()
    for m in range(M):
        h, w = LI()
        HList[h-1] += 1
        WList[w-1] += 1
        graph.add((h-1, w-1))

    Hmax = max(HList)
    Wmax = max(WList)

    HIndex = [i for i, v in enumerate(HList) if v == Hmax]
    WIndex = [i for i, v in enumerate(WList) if v == Wmax]

    ans = Hmax + Wmax
    for h in HIndex:
        for w in WIndex:
            if not (h, w) in graph:
                print(ans)
                return

    print(ans-1)


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

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<32, 1<<32, N*(N-1)//4, N*(N-1)//4
    f = 1
    while r - l > 0.000000001:
        m = (l+r) / 2
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**40)<<16)+i for i, (s, t) in enumerate(Z)])]
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = c - N*(N-1)//4
        else:
            r = m
            rc = max(N*(N-1)//4 - c, 1)
        
        f ^= 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))


### FIXED CODE ###

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<28, 1<<28, N*(N-1)//4+1, N*(N-1)//4+1
    f = 1
    while (r - l) / max(abs(l), 1) > 0.000000001:
        m = (l+r) / 2 if f else (l * rc + r * lc) / (lc + rc)
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**40)<<16)+i for i, (s, t) in enumerate(Z)])]
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = (c - N*(N-1)//4) * 2
        else:
            r = m
            rc = (N*(N-1)//4 - c) * 2 + 1
        f ^= 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))
### BUGGY CODE ###

import itertools
N = int(input())

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

listarray = itertools.combinations(L,3)
count = 0

for items in listarray:
  a = items[0]
  b = items[1]
  c = items[2]
  if a < b + c and b < c + a and c < a + b:
    count +=1

print(count)

### FIXED CODE ###

from bisect import bisect_left

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

L.sort()

ans = 0
for i in range(N - 2):
  a = L[i]
  for j in range(i + 1, N - 1):
    b = L[j]
    c = bisect_left(L, a + b)
    ans += c - j - 1

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

N = int(input())
A = [int(i) for i in input().split(' ')]
count = 0
answer = 0

A.sort()

for i in range(A[0],A[N-1]+1):
    count = 0
    for a in A:
        if i-1 <= a <= i+1:
            count += 1
    if answer < count:
        answer = count
print(answer)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split(' ')]
A.sort()
B = [0]*(A[N-1]+3)

for a in A:
    B[a] += 1
    B[a+1] += 1
    B[a+2] += 1

print(max(B))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    N,K = map(int,raw_input().split())
    A = sorted([int(raw_input()) for i in range(0,K)])

    if (N,K) == (0,0):
        break

    if A[0] == 0:
        flag = True
        A = A[1:]
        K -= 1
    else:
        flag = False

    ans = 0
    for i in range(K):
        for j in range(i+ans,K):
            if j - i == A[j] - A[i]:
                ans = max(ans,A[j]-A[i])
            elif flag is True and j - i + 1 == A[j] - A[i]:
                ans = max(ans,A[j]-A[i])
            else:
                break

    print(ans+1)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    N,K = map(int,raw_input().split())
    A = sorted([int(raw_input()) for i in range(0,K)])

    if (N,K) == (0,0):
        break

    if A[0] == 0:
        flag = True
        A = A[1:]
        K -= 1
    else:
        flag = False

    ans = 0
    count = 0
    diff_list = []
    s = 0
    for i in range(1,K):
        if A[i] - A[i-1] == 2:
            diff_list.append(A[i-1] - A[s])
            s = i
            count = 0
        elif A[i] - A[i-1] > 2:
            diff_list.append(A[i-1] - A[s])
            diff_list.append(0)
            s = i
            count = 0
        else:
            count += 1
            ans = max(ans,count)
    else:
        diff_list.append(A[i] - A[s])

    if flag is True:
        ans = 0
        for i in range(1,len(diff_list)):
            ans = max(ans,diff_list[i] + diff_list[i-1] + 2)

    print(ans + 1)
### BUGGY CODE ###

s = str(input())
t= str(input())

sdict = {}
for i in range(len(s)):
    if s[i] not in sdict:
        sdict[s[i]]=[]
    sdict[s[i]].append(i+1)
    
#print(sdict)

#二分木探索
def search(list_,mark_):
    if  len(list_) == 1:
            return list_[0]
    else:
            mid = len(list_)//2
            if list_[mid-1]>mark_:
                return search(list_[:mid],mark_)
            else:
                return search(list_[mid:],mark_)

ans = 0
mark = 0
for _ in range(len(t)):
    target = t[_]
    if target not in sdict:
        ans = -1
        break
    else:
        if sdict[target][-1]<=mark:
            mark = sdict[target][0]
            ans += len(s)
        elif sdict[target][0]>mark:
            mark = sdict[target][0]
        else:
            posi = search(sdict[target],mark)
            mark = posi
        
if ans != -1:
    ans += mark
print(ans)


### FIXED CODE ###

s = str(input())
t= str(input())

sdict = {}
for i in range(len(s)):
    if s[i] not in sdict:
        sdict[s[i]]=[]
    sdict[s[i]].append(i+1)
    
#print(sdict)

#二分木探索
def search(list_,mark_,sta,gol):
    if  sta == gol:
            return list_[sta]
    else:
            mid = (gol+sta)//2
            if list_[mid]>mark_:
                return search(list_,mark_,sta,mid)
            else:
                return search(list_,mark_,mid+1,gol)

ans = 0
mark = 0
for _ in range(len(t)):
    target = t[_]
    if target not in sdict:
        ans = -1
        break
    else:
        if sdict[target][-1]<=mark:
            mark = sdict[target][0]
            ans += len(s)
        elif sdict[target][0]>mark:
            mark = sdict[target][0]
        else:
            posi = search(sdict[target],mark,0,len(sdict[target])-1)
            mark = posi
        
if ans != -1:
    ans += mark
print(ans)
### BUGGY CODE ###

#coding:utf-8
import random

D = int(input())

C = [int(y) for y in input().split()]

S = []

ans = []

def scoring(inp,poi):
    
    score = 0
    day = 1
    last = [0] * 26
    
    for I in inp:
        score += poi[day-1][I-1]
        last[I-1] = day
        for ind,J in enumerate(last):
            score -= C[ind] * (day - ind - 1)
        day += 1
        
    return score

for i in range(D):
    s = [int(y) for y in input().split()]
    S.append(s)

for i in S:
    k = 0
    num = 0
    for f,t in enumerate(i):
        k = max(k,t)
        if k == t:
            num = f + 1
    ans.append(num)

counter = 10000

base = scoring(ans,S)
nbase = 0
d = 0
ansc = ans.copy()

for i in range(counter):
    p = random.randint(0,25)
    q = random.randint(0,D-1)
    ansc[q] = p
    nbase = scoring(ansc,S)
    if nbase > base:
        ans = ansc.copy()
    else:
        ansc = ans.copy()

for i in ans:
    print("{}".format(int(i)))

### FIXED CODE ###

#coding:utf-8

D = int(input())

C = [int(y) for y in input().split()]

S = []

for i in range(D):
    s = [int(y) for y in input().split()]
    S.append(s)

for i in S:
    k = 0
    num = 0
    for f,t in enumerate(i):
        k = max(k,t)
        if k == t:
            num = f + 1
    print("{}".format(num))
### BUGGY CODE ###

S = input()
 
MOD = 10**9+7
 
dp = [[0]*13 for _ in range(len(S) + 1)]
 
 
dp[0][0] = 1
 
mul = 1
for index in range(len(S)):
    s = S[len(S) - index - 1]
    if s == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i * mul +  pre_index ) % 13
                dp[index+1][next_i] += dp[index][pre_index] 
                dp[index+1][next_i] %= MOD

    else:
        for pre_index in range(13):
            i = int(s)
            next_i = (i * mul  +  pre_index ) % 13
            dp[index+1][next_i] += dp[index][pre_index] 
            dp[index+1][next_i] %= MOD
    mul *= 10
 
 
 
print(dp[len(S)][5])


### FIXED CODE ###

S = input()
 
MOD = 10**9+7
 
dp = [[0]*13 for _ in range(len(S) + 1)]
 
 
dp[0][0] = 1
 
for index in range(len(S)):
    if S[index] == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i +  pre_index * 10 ) % 13
                dp[index+1][next_i] += dp[index][pre_index] 
                dp[index+1][next_i] %= MOD

    else:
        for pre_index in range(13):
            i = int(S[index])
            next_i = (i +  pre_index  * 10) % 13
            dp[index+1][next_i] += dp[index][pre_index] 
            dp[index+1][next_i] %= MOD
 
 
 
print(dp[len(S)][5])
### BUGGY CODE ###

n = int(input())
count = 0
for l in range(1, n+1):
  for i in range(1, 41):
    for j in range(1, 41):
      if (i+j+i)**2-(i*j+j*i+i*i) == l:
        if i == j:   
          count += 1
        else:
          count += 3  
  print(count)
  count = 0    

### FIXED CODE ###

n = int(input())
count = 0
a = [0]*(10**5)
for i in range(1, 100):
  for j in range(1, 100):
    for k in range(1, 100):
      a[(i+j+k)**2-(i*j+j*k+i*k)] += 1


for i in range(n):
  print(a[i+1])
### BUGGY CODE ###

N = int(input())
from_pos, from_neg = [], []
for i, a in enumerate(list(map(int, input().split()))):
  if i%2 == 0:
    from_pos.append(a)
    from_neg.append(-1*a)
  else:
    from_pos.append(-1*a)
    from_neg.append(a)    

ans = []
for i in range(N):
  if i%2== 0:
    ans.append(sum(from_neg[:i])+sum(from_pos[i:]))
  else:
    ans.append(sum(from_pos[:i])+sum(from_neg[i:]))
print(*ans)

### FIXED CODE ###

N = int(input())
alist = list(map(int, input().split()))
m1, m2 = 0, 0
for i, a in enumerate(alist):
  if i == 0:
    m1+=a
    m2+=a
  elif i%2 == 0:
    m1+=a
    m2+=-1*a
  else:
    m1+=-1*a
    m2+=a    

ans = [m1, m2]
for i in range(2, N-1, 2):
  # index=i
  ans.append(ans[i-2] -2*alist[i-2] + 2*alist[i-1])
  # index=i+1
  ans.append(ans[i-1] - 2*alist[i-1] + 2*alist[i])

ans.append(ans[N-3] - 2*alist[N-3] + 2*alist[N-2])

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

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())

row = [[0] * W for _ in range(H)]
line = [[0] * W for _ in range(H)]
ans = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            if i != 0:
                if row[i-1][j] != 0:
                    row[i][j] = row[i-1][j]
                    continue
            c = 1
            if i+c == H:
                row[i][j] = c
                continue
            while S[i+c][j] == '.':
                c += 1
                if i+c == H:
                    break
            row[i][j] = c

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            if j != 0:
                if line[i][j-1] != 0:
                    line[i][j] = line[i][j-1]
                    ans = max(ans, row[i][j]+line[i][j]-1)
                    continue
            c = 1
            if j+c == W:
                line[i][j] = c
                ans = max(ans, row[i][j]+line[i][j]-1)
                continue
            while S[i][j+c] == '.':
                c += 1
                if j+c == W:
                    break
            line[i][j] = c
            ans = max(ans, row[i][j]+line[i][j]-1)


print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())

row = [[0] * W for _ in range(H)]
line = [[0] * W for _ in range(H)]
ans = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            if i != 0:
                if row[i-1][j] != 0:
                    row[i][j] = row[i-1][j]
                    continue
            c = 1
            if i+c == H:
                row[i][j] = c
                continue
            while S[i+c][j] == '.':
                c += 1
                if i+c == H:
                    break
            row[i][j] = c

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            if j != 0:
                if line[i][j-1] != 0:
                    line[i][j] = line[i][j-1]
                    ans = max(ans, row[i][j]+line[i][j]-1)
                    continue
            c = 1
            if j+c == W:
                line[i][j] = c
                ans = max(ans, row[i][j]+line[i][j]-1)
                continue
            while S[i][j+c] == '.':
                c += 1
                if j+c == W:
                    break
            line[i][j] = c
            ans = max(ans, row[i][j]+line[i][j]-1)


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

from bisect import bisect_left
import sys
readline = sys.stdin.readline
N = int(readline())
X = [int(x) for x in readline().split()]
sX = sorted(X)
for i in range(N):
    p = bisect_left(sX, X[i])
    lr = sX[:p] + sX[p+1:]
    print(lr[len(lr) // 2])

### FIXED CODE ###

# O(N * log(Xn))
from bisect import bisect_left
import sys
readline = sys.stdin.readline
N = int(readline())
X = [int(x) for x in readline().split()]

# X = [i for i in range(2*10**5)]
# N = len(X)

sX = sorted(X)
m = (N - 1) // 2
for i in range(N):
    p = bisect_left(sX, X[i])
    if p <= m:
        print(sX[m + 1])
    else:
        print(sX[m])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict


MAX_INT = 2**62-1
sys.setrecursionlimit(10**6)

input = sys.stdin.readline


N = 2 * (10**5) + 1
MOD = 10**9 + 7

fact = [1] * N
fact_inv = [0] * N

for i in range(1, 2 * (10**5)+1):
    fact[i] = fact[i-1] * i % MOD
    fact_inv[i] = pow(fact[i], MOD-2, MOD)


def solve(g):
    def dfs(pre, cur):
        if pre in memo and cur in memo[pre]:
            return memo[pre][cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt)
            num += n
            ways = ways * w % m * fi[n] % m

        ways = ways * f[num-1] % m
        memo[pre][cur] = num, ways
        return num, ways

    m = MOD
    memo = defaultdict(dict)
    f, fi = fact, fact_inv
    print(*[dfs(None, i)[1] for i in range(1, len(g))], sep='\n')


def main():
    n = int(input())
    g = [[] for _ in range(n+1)]

    for _ in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)

    solve(g)


if __name__ == "__main__":

    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from functools import reduce

MAX_INT = 2**62-1
sys.setrecursionlimit(10**7)

input = sys.stdin.readline

# @profile
MOD = 10**9 + 7


def mul_mod(*args, mod=MOD):
    return reduce(lambda a, b: a * b % mod, args)


def solve(g, f, fi, m):
    mul = mul_mod

    stack = [(0, 1)]
    pre_order = []
    n = len(g) - 1

    while stack:
        pre, cur = stack.pop()
        pre_order.append((pre, cur))

        for nxt in g[cur]:
            if nxt == pre:
                continue
            stack.append((cur, nxt))

    size = [1] * (n+1)
    dp = [1] * (n+1)

    for pre, cur in reversed(pre_order):
        dp[cur] = mul(dp[cur], f[size[cur]-1])
        dp[pre] = mul(dp[pre], dp[cur], fi[size[cur]])
        size[pre] += size[cur]

    ans = [1] * (n+1)
    ans[1] = dp[1]

    for pre, cur in pre_order[1:]:
        i = size[cur]
        temp = mul(ans[pre], f[n-i-1], fi[n-1], f[i], pow(dp[cur], m-2, m))
        ans[cur] = mul(f[n-1], temp, fi[n-i], dp[cur], fi[i-1])
    print(*ans[1:], sep='\n')


# @profile
def main():
    mul = mul_mod
    mod = MOD
    n = int(input())
    g = [[] for _ in range(n+1)]

    fact = [1] * (n+1)
    fact_inv = [0] * (n+1)

    for i in range(1, n+1):
        fact[i] = mul(fact[i-1], i)

    fact_inv[-1] = pow(fact[-1], mod-2, mod)

    for i in range(n)[::-1]:
        fact_inv[i] = mul(fact_inv[i+1], (i+1))

    for _ in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)

    solve(g, fact, fact_inv, mod)


if __name__ == "__main__":

    main()
### BUGGY CODE ###

def test(x):
	cost = 0
	for i in range(N):
		cost += max(0, A[i] - (x // F[i]))
	return cost <= K

if __name__ == "__main__":
	N, K = map(int, input().split())
	A = list(map(int, input().split()))
	F = list(map(int, input().split()))
	A.sort()
	F.sort(reverse=True)
	left = -1
	right = 10**13
	while left + 1 < right:
		mid = (left + right) // 2
		if test(mid):
			right = mid
		else:
			left = mid
	ans = right
	print(ans)

### FIXED CODE ###

import numpy as np

def test(x, A, F):
	return np.clip(A - x // F, 0, None).sum() <= K

if __name__ == "__main__":
	N, K = map(int, input().split())
	A = np.array([int(a) for a in input().split()])
	F = np.array([int(a) for a in input().split()])
	A = np.sort(A)
	F = np.sort(F)[::-1]
	left = -1
	right = 10**12 + 1
	while left + 1 < right:
		mid = (left + right) // 2
		if test(mid, A, F):
			right = mid
		else:
			left = mid
	ans = right
	print(ans)
### BUGGY CODE ###

N = int(input())
X = [int(x) for x in input().split()]
X_nm = []
for n in range(N):
  X_nm.append([n, X[n]])
X_nm.sort(key=lambda x:x[1])

for n in range(N):
  idx = X_nm.index([n, X[n]])
  if idx+1 <= N//2:
    ans = X_nm[N//2][1]
    print(ans)
  else:
    ans = X_nm[N//2-1][1]
    print(ans)

### FIXED CODE ###

N = int(input())
X = [int(x) for x in input().split()]

XX = list(tuple(X))
XX.sort()
X_medium_1 = XX[(N//2)-1]
X_medium_2 = XX[N//2]

for n in range(N):
  if X[n] <= X_medium_1:
    print(X_medium_2)
  else: # X[n] >= X_medium_2:
    print(X_medium_1)
### BUGGY CODE ###

N=int(input())
List=list(map(int,input().split()))
cnt=[0 for i in range(max(List)+1)]
for x in List:
  cnt[x]+=1
  
for i in range(1,N+1):
  cnt[List[i-1]]-=1
  print(sum([cnt[j]*(cnt[j]-1)//2 for j in range(len(cnt))])) 
  cnt[List[i-1]]+=1

### FIXED CODE ###

n=int(input())
inp=list(map(int,input().split()))
hoge=[0 for i in range(n)]
huga=[0 for i in range(n)]
for i in inp:
  huga[i-1]+=1
  hoge[i-1]=(huga[i-1]-1)*huga[i-1]
some=sum(hoge)//2
for i in inp:
  if(huga[i-1]==2):
    print(some-1)
  else:
    print(some-int(huga[i-1]-1))
### BUGGY CODE ###

input_line=int(input())
count=0
input_list=[]
while count < input_line:
  input_list.append(input())
  count+=1
ans={}
max_appeard=0
ans_list=[]
list_set=set(input_list)
for item in list_set:
    appeard=input_list.count(item)
    if appeard >= max_appeard:
        max_appeard=appeard
        ans[item]=appeard
for key,value in ans.items():
    if value==max_appeard:
        ans_list.append(key)
ans_list.sort()
for item in ans_list:
  print (item)

### FIXED CODE ###

from collections import defaultdict

H=int(input())
d = defaultdict(int)
for _ in range(H):
    d[input()] += 1
max_appeard=max(d.items(), key=lambda x: x[1])[1]
ans=[k for k,v in d.items() if v == max_appeard]
ans.sort()
for item in ans:
  print (item)