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

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

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

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos, dp):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = max(i for i in range(n+1) if dp[i] < float("inf"))
    for i in range(n):
        if dp[i] == "inf":
            ansl[pos] = i
            break
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v, dp)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0, dp)
flag = False
for i in range(n):
    print(ansl[i])




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

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

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = bisect(dp, 10**18) - 1
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0)
flag = False
for i in range(n):
    print(ansl[i])
### BUGGY CODE ###

k = int(input())

if k%2 ==0:
    print(-1)
    exit(0)

n = 0

for i in range(1, 10**6):
    n += 7 *(10**(i-1))
    if n%k == 0:
        print(i)
        exit(0)

print(-1)

### FIXED CODE ###

k = int(input())

m = 0

for i in range(1, 10**7):
    n = m *10 +7
    m = n % k
    if m == 0:
        print(i)
        exit(0)

print(-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100001)
N, M, K = map(int, input().split())


F, B = {}, {}
for i in range(N):
    F[i] = set()
    B[i] = set()

for _ in range(M):
    x, y = map(int, input().split())
    F[x - 1].add(y - 1)
    F[y - 1].add(x - 1)

for _ in range(K):
    x, y = map(int, input().split())
    B[x - 1].add(y - 1)
    B[y - 1].add(x - 1)


def dfs(v, visited):

    visited.add(v)

    for n in F[v]:
        if n in visited:
            continue
        dfs(n, visited)


for i in range(N):

    C = set()
    dfs(i, C)
    C = C - {i}
    C = C - B[i]
    C = C - F[i]

    print(len(C), end='')
    if i != N - 1:
        print(' ', end='')

print('')


### FIXED CODE ###

import sys
sys.setrecursionlimit(100001)
N, M, K = map(int, input().split())

label = [-1] * N
n_label = [0] * N

F, B = {}, {}
for i in range(N):
    F[i] = set()
    B[i] = set()

for _ in range(M):
    x, y = map(int, input().split())
    F[x - 1].add(y - 1)
    F[y - 1].add(x - 1)

for _ in range(K):
    x, y = map(int, input().split())
    B[x - 1].add(y - 1)
    B[y - 1].add(x - 1)


def dfs(v, lab):
    if label[v] != -1:
        return 0
    label[v] = lab
    n_label[lab] += 1
    for n in F[v]:
        dfs(n, lab)
    return 1


# labeling
count = 0
for i in range(N):
    count += dfs(i, count)
n_label = n_label[:count]

# calc friend candidate
blocked = 0
for b in B[0]:
    if label[b] == label[0]:
        blocked += 1
print(n_label[label[0]] - 1 - len(F[0]) - blocked, end='')
for i in range(1, N):
    print(' ', end='')
    blocked = 0
    for b in B[i]:
        if label[b] == label[i]:
            blocked += 1
    print(n_label[label[i]] - 1 - len(F[i]) - blocked, end='')
print('')
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    A = LI()
    A.sort()
    MAX = 10**6+1
    All = [0] * MAX

    setA = set(A)
    for i in A:
        k = i
        All[k] += 1
        k += i
        if All[i] == 2:
            continue
        while k < MAX:
            All[k] += 1
            k += i

    ans = 0
    for i in range(1, MAX):
        if All[i] == 1 and i in setA:
            ans += 1

    print(ans)

    # oj t -c "pypy3 main.py"
    # acc s main.py -- --guess-python-interpreter pypy
main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    A = LI()
    A.sort()
    MAX = A[-1]+1
    All = [0 for i in range(MAX)]

    setA = set(A)
    for i in A:
        k = i
        All[k] += 1
        k += i
        if All[i] == 2:
            continue
        while k < MAX and i in setA:
            All[k] += 1
            k += i

    ans = 0
    for i in range(1, MAX):
        if All[i] == 1 and i in setA:
            ans += 1

    print(ans)

    # oj t -c "pypy3 main.py"
    # acc s main.py -- --guess-python-interpreter pypy
main()
### BUGGY CODE ###

k,a,b=map(int,input().split())
cnt=1
yen=0

if b<a+2:
    print(k+1)

else:
    for i in range(k):
        if yen>0 :
            cnt+=b
            yen-=1
        elif cnt<a or i==k-1 :
            cnt+=1
        elif cnt>=a and i<=k-2 :
            cnt-=a
            yen+=1

    print(cnt)


### FIXED CODE ###

k,a,b=map(int,input().split())
cnt=0
if b<a+2:
    print(k+1)
else:
    if k>=a+1:
        k-=a+1
        cnt+=b
        q,modulo=divmod(k,2)
        cnt+=q*b-q*a+modulo
        print(cnt)
    else:
        print(k+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_prime_factors(n):
    import numpy as np
    factors = np.arange(0, n+1, 1, dtype=np.int64)
    for i in range(2, n+1):
        if factors[i] == i:
            np.minimum(factors[i*2::i], i, out=factors[i*2::i])
    return factors

#

def main():
    N=ii()
    A=lmis()
    factors = get_prime_factors(10**6)
    d_lcm = defaultdict(int)
    d = [None] * N
    for i, a in enumerate(A):
        d[i] = dd = defaultdict(int)
        p = a
        while p > 1:
            dd[factors[p]] += 1
            p //= factors[p]
        for key in dd.keys():
            d_lcm[key] = max(d_lcm[key], dd[key])
    ans = 0
    for dd in d:
        tmp = 1
        for p in d_lcm.keys():
            tmp *= p ** (d_lcm[p] - dd[p])
            tmp %= N1097
        ans += tmp
        ans %= N1097
    print(ans)


main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    A = lmis()
    l = 1
    for a in A:
        l = lcm(l, a)
    print(sum(l//a for a in A) % N1097)


main()
### BUGGY CODE ###

n= int(input())
s = input()
R = []
G = []
B = []
import bisect
def func(l1,l2,l3,l3set):
  res =0
  for i in l1:
    for j in l2:
      if i>j:
        continue
      a = l3[bisect.bisect_left(l3,j):]
      res += len(a)
      if j*2-i in l3set:
        res -=1
  return res

for i in range(n):
  if s[i] == 'R':
    R.append(i+1)
  elif s[i] == 'G':
    G.append(i+1)
  else:
    B.append(i+1)
    
    
R_set = set(R)
G_set = set(G)
B_set = set(B)
ans = func(R,G,B,B_set)+func(R,B,G,G_set)+func(G,R,B,B_set)+func(G,B,R,R_set) + func(B,R,G,G_set)+func(B,G,R,R_set)
print(ans)
  



### FIXED CODE ###

import sys
input = sys.stdin.readline

n= int(input())
s = input()
R = []
G = []
B = []
import bisect
def func(l1,l2,l3,l3set):
  res =0
  for i in l1:
    for j in l2[bisect.bisect_left(l2,i):]:
      a = l3[bisect.bisect_left(l3,j):]
      res += len(a)
      if j*2-i in l3set:
        res -=1
  return res

for i in range(n):
  if s[i] == 'R':
    R.append(i+1)
  elif s[i] == 'G':
    G.append(i+1)
  else:
    B.append(i+1)
    
    
R_set = set(R)
G_set = set(G)
B_set = set(B)
ans = func(R,G,B,B_set)+func(R,B,G,G_set)+func(G,R,B,B_set)+func(G,B,R,R_set) + func(B,R,G,G_set)+func(B,G,R,R_set)
print(ans)
### BUGGY CODE ###

N = int(input())
s_list = [input() for _ in range(N)]

from collections import Counter
new_s = []
for i, s in enumerate(s_list):
    new_s.append(Counter(sorted(list(s))))

match = []
M=[i for i in range(N)]
center = int(N/2)
count = 0
if N%2==0: # 偶数の時
    for i in range(N-1):
        for i in range(center):
            match.append((M[0+i],M[-1-i]))
        M = M[:1] + M[2:] + M[1:2]
else: # 奇数の時
    for i in range(N):
        for i in range(1,center+1):
            match.append((M[i],M[-i+1]))
        M = M[1:] + M[:1] # １つずつずらす
for m in match:
    if new_s[m[0]] == new_s[m[1]]:
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
s_list = [input() for _ in range(int(N))]
import math
ok = {}
count = 0
for s in s_list:
    s = ''.join(sorted(s))
    if s in ok:
        ok[s] += 1 
    else:
        ok[s] = 1

for val in ok:
    prev = (ok[val] - 1)
    if prev != 0:
        count += math.floor(ok[val] * prev / 2)
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]

for i in range(n):
    b.append(b[i] + a[i])

print(sum([sum([i for i in range(b.count(x))]) for x in set(b)]))

### FIXED CODE ###

from collections import Counter

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

ans = 0

b = [0]
for i in range(n):
	b.append(b[i] + a[i])

c = Counter(b)

for value in c.values():
	ans += value * (value - 1) // 2
    
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
s=0
for i in range(n-2):
    for j in range(i,n-1):
        k=j+1
        t=l[i]+l[j]
        while t>k:
            s+=1
print(s)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
s=0
for i in range(n-2):
    for j in range(i+1,n-1):
        s+=sum([1 for k in l[j+1:] if l[j]<k and k<l[i]+l[j]]) if l[i]<l[j] else 0
print(s)
### BUGGY CODE ###

from math import factorial

def combinations_count(n,r):
    return factorial(n)//(factorial(n-r)*factorial(r))

N=int(input())
A=[]
B=[]
for i in range(N):
    s=input()
    s=sorted(s)
    A.append(s)
    if s not in B:
        B.append(s)

ans=0
for i in range(len(B)):
    if A.count(B[i])>1:
        ans+=combinations_count(A.count(B[i]),2)
print(ans)

### FIXED CODE ###

N=int(input())
P=[]
for i in range(N):
    s=input()
    s=sorted(s)
    P.append(s)

P=sorted(P)
last=P[0]
cnt=0
ans=0
for i in range(1,N):
    if P[i]==last:
        cnt+=1
        ans+=cnt
    else:
        last=P[i]
        cnt=0
print(ans)
### BUGGY CODE ###

import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce
sys.setrecursionlimit(4100000)
from functools import lru_cache
INF = 1 << 60

#ここから書き始める
n, m = map(int, input().split())
a = list(map(int, input().split()))
x = [list(map(int, input().split())) for i in range(m)]
for b, c in x:
    a.extend([c] * b)
a.sort(reverse=True)
# print(a)
print(sum(a[:n]))



### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)
  
for b,c in bc:
  a.extend([c]*b)
  if len(a) > n*2:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

inp = list(map(lambda x: int(x), input().split(" ")))
N = inp[0]
M = inp[1]

dp = [-1]*N

g = {}

def path(x):
    if dp[x-1]!=-1:
        return dp[x-1]
    if not x in g.keys():
        return 0
    else:
        ret = 0
        for k in g[x]:
            if ret<path(k)+1:
                ret = path(k)+1
        dp[x-1] = ret
        return ret

for i in range(M):
    inp = list(map(lambda x: int(x), input().split(" ")))
    x = inp[0]
    y = inp[1]
    if not x in g.keys():
        g[x] = []
    g[x].append(y)

ret = 0
for i in range(1,N+1):
    if ret<path(i):
        ret = path(i)

print(ret)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

inp = list(map(lambda x: int(x), input().split(" ")))
N = inp[0]
M = inp[1]

dp = [-1]*N

g = {}

def path(x):
    if dp[x-1]!=-1:
        return dp[x-1]
    if g[x] == []:
        return 0
    else:
        ret = 0
        for k in g[x]:
            if ret<path(k)+1:
                ret = path(k)+1
        dp[x-1] = ret
        return ret

for i in range(1,N+1):
    g[i] = []

for i in range(M):
    inp = list(map(lambda x: int(x), input().split(" ")))
    x = inp[0]
    y = inp[1]
    g[x].append(y)

ret = 0
for i in range(1,N+1):
    if ret<path(i):
        ret = path(i)

print(ret)
### BUGGY CODE ###

# https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
from math import ceil
import sys
sys.setrecursionlimit(10**7)

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

	# [l. r)
	def get(self, l, r):
		return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s
rh_s, rh_t = RollingHash(s_concat, BASE, MOD), RollingHash(t, BASE, MOD)
t_hash = rh_t.get(0, nt)

adj = [[] for _ in range(ns)]
for i in range(ns):
	if rh_s.get(i, i+nt) == t_hash:
		if i == (i+nt)%ns:
			print(-1)
			sys.exit()
		adj[i].append((i+nt)%ns)

path_len = [0 for _ in range(ns)]

def dfs(x, root):
	if not adj[x]:
		return 0
	v = adj[x][0]
	if v == root:
		print(-1)
		sys.exit()
	else:
		path_len[x] = dfs(v, root) + 1
		return path_len[x]

ans = 0
for i in range(ns):
	if path_len[i] == 0:
		d = dfs(i, i)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)

### FIXED CODE ###

# https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
import sys
def input():
	return sys.stdin.readline()[:-1]

BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			# case of letters
			h[i+1] = v = (v * base + ord(s[i])) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

	# [l. r)
	def get(self, l, r):
		return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod

s = input()
s_concat = s
t = input()
ns, nt = len(s), len(t)

if ns == 1:
	if {s} == set(list(t)):
		print(-1)
	else:
		print(0)
	sys.exit()

while len(s_concat) < ns + nt - 1:
	s_concat += s
rh_s, rh_t = RollingHash(s_concat, BASE, MOD), RollingHash(t, BASE, MOD)
t_hash = rh_t.get(0, nt)

adj = [-1 for _ in range(ns)]
for i in range(ns):
	if rh_s.get(i, i+nt) == t_hash:
		if i == (i+nt)%ns:
			print(-1)
			sys.exit()
		adj[i] = (i+nt)%ns

visited = [False for _ in range(ns)]
path_len = [0 for _ in range(ns)]

def dfs(x):
	cur = x
	res = 0
	while adj[cur] >= 0:
		visited[cur] = True
		if adj[cur] == x:
			print(-1)
			sys.exit()
		res += 1
		if path_len[adj[cur]] > 0:
			path_len[x] = path_len[adj[cur]] + res
			return path_len[adj[cur]] + res
		cur = adj[cur]
	path_len[x] = res
	return res

ans = 0
for i in range(ns):
	if not visited[i]:
		d = dfs(i)
		ans = max(ans, d)

if ans == ns:
	print(-1)
else:
	print(ans)
### BUGGY CODE ###

S=input()
N=len(S)
#dp?
ans=0
for l in range(N-4):
    r=l+4
    X=S[l:r+1]
    on=False
    while r<N:
        T=int(X)
        if T%(2019)==0:
            ans+=1
            if not on:
                add=r-l+1
                on=True
        if on:
            
            X+=S[r+1:r+add+1]
            r+=add
        else:
            r+=1
            X+=S[min(r,N-1)]
print(ans)

### FIXED CODE ###

S=input()
N=len(S)
R=[0]*(N+1)
mul=1
for i in range(1,N+1):
    R[-(i+1)]=(((int(S[-i])*mul))%(2019)+R[-i])%2019
    mul*=10
    mul%=2019
#print(R)
L=[0]*2019
for r in R:
    L[r]+=1
ans=0
for l in L:
    if l>=2:
        ans+=l*(l-1)//2
print(ans)
### BUGGY CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

card = A.copy()
for B,C in BC:
    card += [C]*B

card.sort(reverse=True)
print(sum(card[:len(A)]))

### FIXED CODE ###

N, M = map(int,input().split())
A = [[1,int(a)] for a in input().split()]
BC = A + [list(map(int,input().split())) for _ in range(M)]

BC.sort(key=lambda x:x[1], reverse=True)

i = 0
ans = 0
for B,C in BC:
    if i + B <= N:
        ans += B*C
        i += B
    else:
        ans += (N - i) * C
        break

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

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


count = 0
for i in range(N):
    is_ans = True
    for j in range(N):
        if i != j:
            if A[i] % A[j] == 0:
                is_ans = False
                break

    if is_ans:
        count += 1

print(count)


### FIXED CODE ###

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


def solve2(N, A):
    A.sort()
    amax = A[-1]
    dp = [True] * (amax + 1)
    cnt = [0] * (amax + 1)

    for a in A:
        cnt[a] += 1

    for i in range(amax):
        x = i + 1
        if cnt[x] > 1:
            dp[x] = False

        if cnt[x] > 0:
            y = x * 2
            while y <= amax:
                dp[y] = False
                y += x

    ansval = [x for x in A if dp[x]]

    # print(ansval)
    ans = len(ansval)

    return ans


def solve1(N, A):
    ans = 0
    for i in range(N):
        is_ans = True
        for j in range(N):
            if i != j:
                if A[i] % A[j] == 0:
                    is_ans = False
                    break

        if is_ans:
            ans += 1

    return ans


print(solve2(N, A))
### BUGGY CODE ###

T = input()
out = ""
i = 0
while(i < len(T)):
  if T[i] == "?":
    if (i+1 != len(T)) & (i-1 != -1):
      if T[i+1]=="D": 
        out += "P"
        i += 1
      elif T[i-1]=="P": 
        out += "D"
        i += 1
      elif T[i+1]=="?":
        out += "PD"
        i += 2

    elif (i+1 == len(T)):
      out += "D"
      i += 1

    elif (i-1 == -1):
      if T[i+1]=="D": 
        out += "P"
        i += 1
      elif T[i+1]=="P": 
        out += "D"
        i += 1
      elif T[i+1]=="?":
        out += "PD"
        i += 2

  else:
    out += T[i]
    i += 1

  #print(out)

print(out)


### FIXED CODE ###

T = input()
T_l = [t for t in T]

for i in range(len(T_l)):
  if T[i] =="?": T_l[i] = "D"

print("".join(T_l))
### BUGGY CODE ###

Q = int(input())
INF = 10 ** 9

queries = []
for _ in range(Q):
    queries.append(input())

from bisect import insort_left

ary, absum, bsum, c = [], 0, 0, 0
left, right = -INF, INF
for query in queries:
    if query[0] == '2':
        # absum = sum(abs(a - ary[(c-1)//2]) for a in ary)
        # absum = asum - (c//2 + 1) * ary[(c-1)//2]
        print(' '.join(map(str, (ary[(c-1)//2], absum + bsum))))
    else:
        _, a, b = map(int, query.split())
        insort_left(ary, a)
        c += 1
        if left <= a <= right:
            absum += 0
        elif a < left:
            absum += left - a
        else:
            absum += a - right
        left, right = ary[(c-1)//2], ary[c - (c-1)//2 - 1]        
        bsum += b


### FIXED CODE ###

Q = int(input())
INF = 10 ** 9

queries = []
for _ in range(Q):
    queries.append(input())

from bisect import insort_left
from heapq import heappush, heappop

absum, bsum, c = 0, 0, 0
# left, right = -INF, INF
lefts, rights = [INF], [INF]
for query in queries:
    if query[0] == '2':
        # absum = sum(abs(a - ary[(c-1)//2]) for a in ary)
        # absum = asum - (c//2 + 1) * ary[(c-1)//2]
        # print(' '.join(map(str, (ary[(c-1)//2], absum + bsum))))
        # print(str(ary[(c-1)//2]) + ' ' + str(absum + bsum))
        print(-lefts[0], absum + bsum)
    else:
        _, a, b = map(int, query.split())
        if c % 2 == 0:
            if -lefts[0] <= a <= rights[0]:
                heappush(lefts, -a)
                heappush(rights, a)
                absum += 0
            elif a < -lefts[0]:
                heappush(lefts, -a)
                heappush(rights, -lefts[0])
                absum += -lefts[0] - a
            else:
                heappush(rights, a)
                heappush(lefts, -rights[0])
                absum += a - rights[0]
        else:
            if a < -lefts[0]:
                absum += -lefts[0] - a
                heappop(lefts)
                heappush(lefts, -a)
            else:
                absum += a - rights[0]
                heappop(rights)
                heappush(rights, a)
        # left, right = ary[(c-1)//2], ary[c - (c-1)//2 - 1]        
        bsum += b
        c += 1
### BUGGY CODE ###

N=int(input())

S=str(input())

#W=左
#E=右
ans=1000000000000
for i in range(N-1):
    count=0
    SL="".join(S[0:i])
    SR="".join(S[i+1:len(S)])
    #print(SL+"と"+SR)
    #print(SL.count("W"))
    #print(SR.count("E"))
    count=SL.count("W")+SR.count("E")
    ans=min(ans,count)

print(ans)

### FIXED CODE ###

N=int(input())
S=str(input())
#W=左
#E=右
ans=[]
count=0
#一番左
for i in range(1,N):
    
    if S[i]=="E":
        count+=1    
        
        
ans.append(count)


for i in range(1,N):
    
    if S[i-1]=="W":
        count+=1
    if S[i]=="E":
        count-=1

    ans.append(count)

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

h,w=map(int,input().split())
l=list()
l.append('#'*(w+2))
for i in range(h):
    l.append("#"+input()+"#")
l.append('#'*(w+2))
si=[[0 for i in j] for j in l]
sj=[[0 for i in j] for j in l]
for i in range(h+2):
    k=0
    for j in range(w+2):
        if l[i][j]==".":
            k+=1
        else:
            for f in range(j-k,j):
                si[i][f]=k
            k=0
for j in range(w+2):
    k=0
    for i in range(h+2):
        if l[i][j]==".":
            k+=1
        else:
            for f in range(i-k,i):
                sj[f][j]=k
            k=0
ans=0
for i in range(h+2):
    for j in range(w+2):
        ans=max(ans,sj[i][j]+si[i][j])
print(ans-1)

### FIXED CODE ###

h,w=map(int,input().split())
l=list()
l.append('#'*(w+2))
for i in range(h):
    l.append("#"+input()+"#")
l.append('#'*(w+2))
si=[[0 for i in j] for j in l]
sj=[[0 for i in j] for j in l]
for i in range(h+2):
    k=0
    for j in range(w+2):
        if l[i][j]==".":
            k+=1
        else:
            for f in range(j-k,j):
                si[i][f]=k
            k=0
for j in range(w+2):
    k=0
    for i in range(h+2):
        if l[i][j]==".":
            k+=1
        else:
            for f in range(i-k,i):
                sj[f][j]=k
            k=0
ans=0
for i in range(h+2):
    for j in range(w+2):
        ans=max(ans,sj[i][j]+si[i][j])
print(ans-1)