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

X = input()
for i in range(10 ** 1000):
  p = X.find('ST')
  if p == -1:
    break
  X = ''.join([X[:p],X[p + 2:]])
print(len(X))  

### FIXED CODE ###

X = input()
cnt = 0
res = 0
for i in X:
  if i == 'S':
    cnt += 1
  else:
    if cnt > 0:
      cnt -= 1
    else:
      res += 1
print(cnt + res)
### BUGGY CODE ###

import math
from collections import defaultdict
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:list(input())

"""========main code==============="""
t=ii()

a=ll()
s=1
f=0
val=10**18
for i in a:
    s*=i
    
if s>val:
    print(-1)
else:
    print(s)


### FIXED CODE ###

import math
from collections import defaultdict
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:list(input())

"""========main code==============="""
t=ii()

a=ll()
s=1
f=0
val=10**18
if 0 in a:
    print(0)
else:    
    for i in a:
        s*=i
        if(s>val):
            f=1
            break
    if f:
        print(-1)
    else:
        print(s)
### BUGGY CODE ###

n, = map(int, input().strip().split())

# a5 - b5 = (a-b)(a4 + a3b + a2b2 + ab3 + b4)

def check(x):
  for a in range(n+1):
    b = a - x
    c = a**4 + a**3 * b + a**2 * b**2 + a * b**3 + b**4
    d = x * c 
    if d == n:
      return [a, b]

    a += 1
  return None

for i in range(1, n+1):
  res = check(i)
  if res:
    break

r1, r2 = res
print(r1, r2)

### FIXED CODE ###

n, = map(int, input().strip().split())

# a5 - b5 = (a-b)(a4 + a3b + a2b2 + ab3 + b4)

def check(x):
  for a in range(200):
    b = a - x
    c = a**4 + a**3 * b + a**2 * b**2 + a * b**3 + b**4
    d = x * c
    if d == n:
      return [a, b]
  return None

for i in range(1, n+1):
  res = check(i)
  if res:
    break

r1, r2 = res
print(r1, r2)
### BUGGY CODE ###

import sys
from _operator import itemgetter

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

N, W = na()
maxV = 10 ** 5
dp = [[10**9+7] * (maxV+1) for i in range(N+1)]  # dp[i][v] i番目までで価値がvの時の重さの合計の最小値
dp[0][0] = 0
tp = [na() for i in range(N)]
list.sort(tp, key=itemgetter(0))
for i in range(1, N+1):
    wi, vi = tp[i - 1]
    for v in range(1, maxV+1):
        if v - vi >= 0:
            dp[i][v] = min(dp[i - 1][v], dp[i - 1][v - vi] + wi)
        else:
            dp[i][v] = dp[i - 1][v]
ans = -1
for i in range(1, N + 1):
    for v in range(1, maxV+1):
        if dp[i][v] <= W:
            ans = max(ans, v)
print(ans)

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

N, W = na()
maxV = 10 ** 5
dp = [[10**9+7] * (maxV+1) for i in range(N+1)]  # dp[i][v] i番目までで価値がvの時の重さの合計の最小値
dp[0][0] = 0
tp = [na() for i in range(N)]
list.sort(tp, key=lambda x:x[0])
for i in range(1, N+1):
    wi, vi = tp[i - 1]
    for v in range(1, maxV+1):
        if v - vi >= 0:
            dp[i][v] = min(dp[i - 1][v], dp[i - 1][v - vi] + wi)
        else:
            dp[i][v] = dp[i - 1][v]
ans = -1
for i in range(1, N + 1):
    for v in range(1, maxV+1):
        if dp[i][v] <= W:
            ans = max(ans, v)
print(ans)
### BUGGY CODE ###

# D
s = input()
length = len(s)
k = length
mid = length//2
max_k = None

while k>mid:
    overlap = s[length-k:k]
    pure = len(set(overlap)) == 1
    if pure:
        max_k = k
        print(max_k)
        break
    k -= 1

if not max_k:
    print(mid)

### FIXED CODE ###

# D 3424320
S = input()
N = len(S)
center_i = N//2
center = S[center_i]

ans = N//2
l = r = center_i
if N%2==0:
    l -= 1
while l >= 0:
    if not (S[l] == center == S[r]):
        break
    l -= 1
    r += 1
    ans += 1
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
def dfs(num,hiyo):
    ans[num]=hiyo
    for item in way[num]:
        if ans[item]==-1:
            dfs(item,hiyo+cost[num][item])
    
    return 

N=int(input())

way=[[] for i in range(N)]
cost=[[0]*N for i in range(N)]
ans=[-1]*N

for _ in range(N-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    way[u].append(v)
    way[v].append(u)
    cost[u][v]=w
    cost[v][u]=w

#lis.sort(key=lambda x:(x[0],x[1]))

dfs(0,0)

for item in ans:
    print(item%2)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
 
sys.setrecursionlimit(10**7)

def dfs(num,hiyo):
    ans[num]=hiyo
    for to,cos in way[num]:
        if ans[to]==-1:
            dfs(to,hiyo+cos)
    
    return 

N=int(input())

way=[[] for i in range(N)]
ans=[-1]*N

for _ in range(N-1):
    u,v,w=map(int,input().split())
    u-=1
    v-=1
    way[u].append([v,w])
    way[v].append([u,w])

#lis.sort(key=lambda x:(x[0],x[1]))

dfs(0,0)
#print(ans)
for item in ans:
    print(item%2)
### BUGGY CODE ###

from _collections import deque

S = list(input())
dp = [ [0]*2020 for _ in range(len(S)+1) ]
dp[0][0] = 1
A = [0]
for i in range(1,len(S)+1):
    q = deque(A)
    A = []
    while(len(q)>0):
        j = q.popleft()
        T = (j * 10 + int(S[i - 1])) % 2019
        dp[i][T] += dp[i-1][j]
        A.append(T)
    if i != 1:
        dp[i][int(S[i-1])] += 1
        A.append(int(S[i-1]))

ans = 0
for i in range(1,len(S)+1):
    ans += dp[i][0]
print(ans)

### FIXED CODE ###

from collections import Counter

S = list(input())
T = [int(S[len(S)-1])]
k = int(S[len(S)-1])
for i in range(len(S)-2,-1,-1):
    k = (int(S[i])*pow(10,len(S)-i-1,2019) + k ) % 2019
    T.append(k)

A = Counter(T)
ans = 0
ans += A.get(0,0)
for i in A.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys
def expect(x):
    return sum(list(range(1,x+1)))/x
input = sys.stdin.readline
n, k = map(int, input().split())
p = list(map(int, input().split()))
table = []
for i in range(n-k+1):
    w = 0
    for j in range(k):
        w += expect(p[i+j])
    table.append(w)
print(max(table))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, k = map(int,input().split())
p = list(map(int, input().split()))
p = [(1+i)/2 for i in p]
# 累積和の配列sを作成する
s = [0] * (n+1)
for i in range(1,n+1):
    s[i] = s[i-1] + p[i-1]
max = -1 * float("inf")
for i in range(n-k+1):
    sum = s[k+i] - s[i]
    if max <= sum:
        max = sum
print(max)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
cnt = 0

for j in range(n-1):
  for k in range(j+1,n):
    if sorted(s[j]) == sorted(s[k]):
      cnt += 1
      
print(cnt)

### FIXED CODE ###

from collections import Counter
n = int(input())
cnt_s = Counter([" ".join(sorted(input())) for i in range(n)])
print(sum(v*(v - 1)//2 for v in cnt_s.values()))
### BUGGY CODE ###

def f(x, A, B):
    return ((A*x)//B) - A*(x//B)

def main():
    A, B, N = map(int, input().split())
    ans = -1
    for x in range(min(B, N), max(min(B, N)-N, -1), -1):
        ans = max(ans, f(x, A, B))
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def f(x, A, B):
    return ((A*x)//B) - A*(x // B)

def main():
    A, B, N = map(int, input().split())
    ans = -1
    for x in range(min(B-1, N), max(min(B-1, N)-N, -1), min(-B+1, -1)):
        ans = max(ans, f(x, A, B))
    print(ans)

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

N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
dp = [0 for i in range(N)]

mod = 10**9+7

for i in range(0, N)[::-1]:
    if i in a:
        dp[i] = 0
        continue
    if i == N-1:
        dp[N - 1] = 1
        continue
    if i == N-2:
        dp[N - 2] = 1 + dp[N - 1]
        continue
    dp[i] = (dp[i+1] + dp[i+2])%mod

print(dp[0])

### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
dp = [0 for i in range(N)]

mod = 10**9+7
stair_set = set(range(0, N)[::-1])
stair_set = stair_set - set(a)
stair_list = list(stair_set)
stair_list.sort(reverse=True)

for i in stair_list:
    if i == N-1:
        dp[N - 1] = 1
        continue
    if i == N-2:
        dp[N - 2] = 1 + dp[N - 1]
        continue
    dp[i] = (dp[i+1] + dp[i+2])%mod

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

n,m,k=map(int,input().split())
par=[i for i in range(n)]
rank=[0 for i in range(n)]
# this par & rank are initialized lists
def find_par(x):
    global par
    if par[x]==x:
        return x
    else:
        par[x]= find_par(par[x])
        return par[x]
def unite(x,y):
    x,y=find_par(x),find_par(y)
    global rank,par
    if x==y:return
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1
def same(x,y):
    return find_par(x)==find_par(y)
friend=[set() for i in range(n)]
for i in range(m):
    a,s=map(int,input().split())
    a-=1;s-=1
    unite(a,s)
    friend[a].add(s)
    friend[s].add(a)
G=[find_par(i)  for i in range(n)]
anti=[set() for i in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    a-=1;b-=1
    anti[a].add(b)
    anti[b].add(a)
friends=[set() for i in range(n)]
for i in range(n):
    friends[par[i]].add(i)
psfriend=[friends[par[i]] for i in range(n)]

print(*[len(psfriend[i]-anti[i]-friend[i]-set([i])) for i in range(n)],sep=" ")


### FIXED CODE ###

n,m,k=map(int,input().split())
par=[-1]*n

# this par & rank are initialized lists
def find(x):
    global par
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
        
def unite(x,y):
    x,y=find(x),find(y)
    global par
    if x==y:return False
    else:
        if par[x]>par[y]:x,y=y,x
        par[x]+=par[y]
        par[y]=x
        return True

def size(x):
    return -par[find(x)]
def same(x,y):
    return find(x)==find(y)
from sys import stdin 
input=stdin.readline
friend=[0]*n
for i in range(m):
    a,s=map(int,input().split())
    a-=1;s-=1
    unite(a,s)
    friend[a]+=1
    friend[s]+=1
anti=[set() for i in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    a-=1;b-=1
    anti[a].add(b)
    anti[b].add(a)

print(*[size(i)-1-sum(same(i,b) for b in anti[i])-friend[i] for i in range(n)],sep=" ")
### BUGGY CODE ###

(h, n), *m = [[*map(int, i.split())] for i in open(0)]
dp = [0] + [10**9] * h
for i in range(1, h + 1):
    for a, b in m:
        dp[i] = min(dp[i], dp[max(i-a,0)]+b)
print(dp[-1])


### FIXED CODE ###

(h, n), *m = [[*map(int, i.split())] for i in open(0)]
dp = [0] + [10**9] * h
for i in range(1, h + 1):
    for a, b in m:
        dp[i] = min(dp[i], dp[max(i-a,0)]+b)
print(dp[-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
s = int(input())
ans = 0
MOD = 10**9 + 7
def dfs(A):
    # print(A)
    global ans
    summ = sum(A)
    if summ == s:
        ans += 1
        ans %= MOD
        return False
    elif summ < s:
        for i in range(3, s+1):
            if s - summ < 3:
                break
            A.append(i)
            if dfs(A) == False:
                A.pop()
                break
            A.pop()
        return True
    else:
        return False

dfs([])
print(ans%MOD)

### FIXED CODE ###

s = int(input())
MOD = 10 ** 9 + 7
ans = 0
fact = [0] * 10000
fact[0], fact[1] = 1, 1
for i in range(2, 10000):
    fact[i] = (fact[i-1] * i) % MOD

def f(n, r):
    return fact[n] * pow(fact[n-r], -1, MOD) * pow(fact[r], -1, MOD)

for i in range(1, s//3+1):
    if i == 1:
        ans += 1
    else:
        m = s - i * 3
        ans += f(m+i-1, m)
        ans %= MOD
print(ans%MOD)
### BUGGY CODE ###

h,w=map(int, input().split())
ch,cw=map(int, input().split())
ch-=1
cw-=1
dh,dw=map(int, input().split())
dh-=1
dw-=1
grid=[]
es=[[] for _ in range(h*w)]

for i in range(h):
    s=input()
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=set([(1,0),(-1,0),(0,1),(0,-1)])
warp=set([(i,j) for i in range(-2,3) for j in range(-2,3)])
warp=warp.difference(dif.union({(0,0)}))

for i in range(h):
    for j in range(w):
        if grid[i][j]==-1:
            continue
        else:
            for d0,d1 in dif:
                newi=i+d0
                newj=j+d1
                if 0<=newi<h and 0<=newj<w and grid[newi][newj]!=-1:
                    es[i*w+j].append([newi*w+newj, 0])
            for d0,d1 in warp:
                newi=i+d0
                newj=j+d1
                if 0<=newi<h and 0<=newj<w and grid[newi][newj]!=-1:
                    es[i*w+j].append([newi*w+newj, 1])

from heapq import heappush, heappop
def dijkstra(edges, size, source, goal):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        if v==goal:
            break
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance[goal]

dist=dijkstra(es,h*w,ch*w+cw,dh*w+dw)
if dist==float('inf'):
    print(-1)
else:
    print(dist)

### FIXED CODE ###

h,w=map(int, input().split())
ch,cw=map(int, input().split())
ch-=1
cw-=1
dh,dw=map(int, input().split())
dh-=1
dw-=1
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            grid[i][j]=col
            while stack:
                nowi,nowj=stack.popleft()
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                        grid[nowi+di][nowj+dj]=col
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()
es=[set([]) for _ in range(col)]
visited=[-1]*col

for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])
### BUGGY CODE ###

n,k=map(int,input().split())
a=[(2*k+1)*[0]for _ in range(2*k+1)]
for _ in range(n):
  x,y,c=input().split()
  x=int(x)
  y=int(y)
  if c=="B":y+=k
  x%=2*k
  y%=2*k
  a[x+1][y+1]+=1
ans=0
for i in range(1,2*k+1):
  for j in range(1,2*k+1):a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]
for i in range(k,2*k+1):
  for j in range(k,2*k+1):
    t=a[i][j]-a[i-k][j]-a[i][j-k]+a[i-k][j-k]
    t+=a[i-k][j-k]
    t+=a[2*k][j-k]-a[i][j-k]
    t+=a[i-k][2*k]-a[i-k][j]
    t+=a[2*k][2*k]-a[i][2*k]-a[2*k][j]+a[i][j]
    ans=max(ans,t,n-t)
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
a=[(2*k+1)*[0]for _ in range(2*k+1)]
for _ in range(n):
  x,y,c=input().split()
  x=int(x)
  y=int(y)
  if c=="B":y+=k
  x%=2*k
  y%=2*k
  a[x+1][y+1]+=1
ans=0
for i in range(1,2*k+1):
  for j in range(1,2*k+1):a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]
for i in range(k,2*k+1):
  for j in range(k,2*k+1):
    t=a[i][j]-a[i-k][j]-a[i][j-k]+a[i-k][j-k]
    t+=a[i-k][j-k]
    t+=a[2*k][j-k]-a[i][j-k]
    t+=a[i-k][2*k]-a[i-k][j]
    t+=a[2*k][2*k]-a[i][2*k]-a[2*k][j]+a[i][j]
    ans=max(ans,t,n-t)
print(ans)
### BUGGY CODE ###

s = list(input())
t = list(input())
q = int(input())

def check(x, y):
	xa = len(list(filter(lambda i: i == "A", x)))
	ya = len(list(filter(lambda i: i == "A", y)))
	if (2 * xa - len(x)) % 3 == (2 * ya - len(y)) % 3:
		print("YES")
	else:
		print("NO")

for _ in range(q):
	a, b, c, d = map(int, input().split())
	check(s[a - 1 : b], t[c - 1 : d])

### FIXED CODE ###

s = input()
t = input()
q = int(input())

sa_pre = [s[i] == "A" for i in range(len(s))]
ta_pre = [t[i] == "A" for i in range(len(t))]

sa = [0, sa_pre[0]]
ta = [0, ta_pre[0]]

for i in range(1, len(s)):
	sa.append(sa[-1] + sa_pre[i])

for i in range(1, len(t)):
	ta.append(ta[-1] + ta_pre[i])

def check(a, b, c, d):
	xa = sa[b] - sa[a - 1]
	ya = ta[d] - ta[c - 1]
	if (2 * xa - (b - a + 1)) % 3 == (2 * ya - (d - c + 1)) % 3:
		print("YES")
		return
	else:
		print("NO")
		return

for _ in range(q):
	a, b, c, d = map(int, input().split())
	check(a, b, c, d)
### BUGGY CODE ###

k, q = map(int, input().split())
d = list(map(int, input().split()))
for _ in range(q):
  n, x, m = map(int, input().split())
  dmod = [di % m for di in d]
  same = dmod.count(0) * ((n-1) // k) + dmod[: (n-1) % k].count(0)
  a_last = x + sum(dmod) * ((n-1) // k) + sum(dmod[: (n-1) % k])
  beyond = a_last // m - x // m
  print(n - 1 - same - beyond)

### FIXED CODE ###

import numpy as np

k, q = map(int, input().split())
d = np.array(input().split(), dtype=np.int)
for _ in range(q):
  n, x, m = map(int, input().split())
  quot = (n-1) // k
  rest = (n-1) % k
  dmod = d % m
  same = (k - np.count_nonzero(dmod)) * quot + rest - np.count_nonzero(dmod[:rest])
  a_last = x % m + dmod.sum() * quot + dmod[:rest].sum()
  beyond = a_last // m
  print(n - 1 - same - beyond)
### BUGGY CODE ###

n,m = map(int,raw_input().split())
keys = []
for i in xrange(m):
	a,b = map(int,raw_input().split())
	c = map(int,raw_input().split())
	mask = 0
	for x in c:
		mask += 2**(x-1)
	keys.append((mask,a))
#print(keys)
dp = []
M = 2**n
for i in xrange(m+1):
	dp.append([10**9]*M)
	dp[i][0] = 0
	
for i in xrange(m):
	key = keys[i]
	for j in xrange(M):
		dp[i+1][j|key[0]] = min(dp[i+1][j|key[0]], dp[i][j]+key[1])
		dp[i+1][j] = min(dp[i+1][j], dp[i][j])

if dp[m][M-1] >= 10**9:
	print -1
else:
	print dp[m][M-1]

### FIXED CODE ###

n,m = map(int,raw_input().split())

M = 1<<n
dp = [10**9]*M
dp[0] = 0
for i in xrange(m):
	a,b = map(int,raw_input().split())
	c = map(int,raw_input().split())
	mask = 0
	for x in c:
		mask += 1<<(x-1)
	for j in xrange(M):
		dp[j|mask] = min(dp[j|mask], dp[j]+a)
	#print dp
 
if dp[M-1] >= 10**9:
	print -1
else:
	print dp[M-1]
### BUGGY CODE ###

def shell_sort(array):
    n = len(array)
    h = 0
    k = 0
    cnt = 0
    g = []
    while h <= n/9:
        h = 3*h + 1
        g.append(h)
    while g[k] > 0:
        for i in range(h,n):
            tmp = array[i]
            if tmp < array[i-g[k]]:
                j = i
                while True:
                    array[j] = array[j-g[k]]
                    j -= h
                    cnt += 1
                    if j < h or tmp >= array[j-g[k]]:
                        break
                array[j] = tmp
    print(len(g))
    print(*g)
    print(cnt)
    for i in range(array): print(array[i])

d = []
for i in range(int(input())):
    d.append(int(input()))
shell_sort(d)
    


### FIXED CODE ###

def insertionSort(A,n,g):
    cnt = 0
    for i in range(g,n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
            A[j+g] = v
    return cnt
    
def shellsort(A,n):
    cnt = 0
    h = 1
    G = []
    while h <= n:
        G.append(h)
        h = 3*h + 1
    G.reverse()
    m = len(G)
    print(m)

    print(" ".join(map(str,G)))
    for i in range(m):
        cnt += insertionSort(A,n,G[i])
    print(cnt)
    for i in A:
        print(i)
        
n = int(input())
A = []
for _ in range(n):
    A.append(int(input()))
shellsort(A,n)
### BUGGY CODE ###

import random

n = int(input())
L = list(range(n))
random.shuffle(L)
K = []
now = -1
for a in L:
  print(a, flush=True)
  t = input()
  if t == "Vacant":
    exit()
  if now == -1:
    now = t
    K.append(a)
  else:
    if now != t:
      m = min(K), M = max(K)
      if abs(m-a) < abs(M-a):
        l, r = m, a
      else:
        l, r = M, a
      l_s, r_s = now, t
      break
    else:
      K.append(a)
if l > r:
  l, r = r, l
  l_s, r_s = r_s, l_s
while True:
  mid = (l+r)//2
  print(mid, flush=True)
  t = input()
  if t == "Vacant":
    exit()
  if t == l_s:
    l = mid
  else:
    r = mid

### FIXED CODE ###

n = int(input())
l, r = 0, n-1
print(0, flush=True)
l_s = input()
if l_s == "Vacant":
  exit()
print(n-1, flush=True)
l_t = input()
if l_t == "Vacant":
  exit()
while True:
  mid = (l+r)//2
  print(mid, flush=True)
  t = input()
  if t == "Vacant":
    exit()
  if ((mid-l)%2 and l_s==t) or ((mid-l)%2==0 and l_s!=t):
    r = mid
  else:
    l = mid
    l_s = t
### BUGGY CODE ###

def main():
    from bisect import bisect_left as bs
    from operator import itemgetter
    n, m, *abc = map(int, open(0).read().split())
    a = sorted(abc[:n])
    *bc, = zip(*[iter(abc[n:])] * 2)
    bc = sorted(bc, key=itemgetter(1), reverse=True)

    ans = 0
    for b, c in bc:
        i = bs(a, c)
        if i == 0:
            break
        j = min(i, b)
        ans += j * c
        a = a[j:]

    print(ans + sum(a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    n, m, *abc = map(int, open(0).read().split())
    a = Counter(abc[:n])
    bc = abc[n:]
    for i, j in zip(*[iter(bc)] * 2):
        a[j] += i

    cnt = n
    ans = 0
    keys = list(a.keys())
    keys.sort(reverse=True)

    for k in keys:
        m = a[k]
        if m <= cnt:
            ans += k * m
            cnt -= m
        else:
            ans += k * cnt
            break

    print(ans)


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

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

for i in range(n):
    print(max(a[:i] + a[i+1:]))


### FIXED CODE ###

n = int(input())
a = {}
for i in range(n):
    a[i] = int(input())

max_i, MAX = max(a.items(), key=lambda x: x[1])
del a[max_i]

SECOND = max(a.values())


for i in range(n):
    if i == max_i:
        print(SECOND)
    else:
        print(MAX)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2*2*10**5)

def dfs(i,p,edges,num):
    
    for j in edges[i]:
        if(j!=p):
            
            num[j] += num[i]
            
            dfs(j,i,edges,num)
    

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


#隣接リスト
edges = [ [] for i in range(N)]
num = [0]*N


for i in range(N-1):
    a0,b0 = map(int,input().split())

    edges[a0-1].append(b0-1)
    edges[b0-1].append(a0-1)
    
for i in range(Q):
    p0,x0 = map(int,input().split())

    num[p0-1] += x0
    
dfs(0,-1, edges, num)
    
for i in range(N):
    print(num[i], end=" ")

### FIXED CODE ###

# https://atcoder.jp/contests/abc138/tasks/abc138_d
import sys
sys.setrecursionlimit(2*2*10**5)

def dfs(i,p,edges,num):
    
    for j in edges[i]:
        if(j!=p):
            
            num[j] += num[i]
            
            dfs(j,i,edges,num)
    
def input():
    return sys.stdin.readline()[:-1]

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


#隣接リスト
edges = [ [] for i in range(N)]
num = [0]*N


for i in range(N-1):
    a0,b0 = map(int,input().split())

    edges[a0-1].append(b0-1)
    edges[b0-1].append(a0-1)
    
for i in range(Q):
    p0,x0 = map(int,input().split())

    num[p0-1] += x0
    
dfs(0,-1, edges, num)
    
for i in range(N):
    print(num[i], end=" ")
### BUGGY CODE ###

N = int(input())
card = [int(i) for i in input().split()]
single = [i for i in card if card.count(i) == 1]
plural = sorted([i for i in card if i not in single])
while len(plural) > 0:
    min_A = plural.pop(0)
    max_A = plural.pop(-1)
    if plural.count(min_A) == 1:
        single.append(plural.pop(0))
    if plural.count(max_A) == 1:
        single.append(plural.pop(-1))

print(len(single))

### FIXED CODE ###

#解説を確認後
N = int(input())
card = set([int(i) for i in input().split()])

if len(card) % 2 == 1:
    print(len(card))
else:
    print(len(card)-1)