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

from operator import itemgetter
from collections import deque
import sys

def main():
    n = int(input())  
    keys = map(lambda i:(map(int,raw_input().split())+[i]),xrange(n))

    keys.sort(key=itemgetter(0))
    id_m = len(keys)/2
    root = Node(keys[id_m][:2],keys[id_m][2])
    if id_m != 0:
        recursive_add_Node(root,keys[:id_m],1)
    if id_m+1 != len(keys):
        recursive_add_Node(root,keys[id_m+1:],1)

    q = int(input())
    for i in xrange(q):
        sx, tx, sy, ty = map(int,raw_input().split())
        nums = deque()
        find(root,[sx,sy],[tx,ty],0,nums)
        nums = list(nums)
        nums.sort()
        map(lambda i:sys.stdout.write("{}\n".format(i)), nums)
        print ("")

def find(z,s,t,d,nums):
    if(s[0]<=z.key[0]<=t[0])and(s[1]<=z.key[1]<=t[1]):
        nums.append(z.num)
    d += 1
    xy = d%2
    if (z.left != None)and(z.key[xy]>=s[xy]):
        find(z.left,s,t,d,nums)    
    if (z.right != None)and(z.key[xy]<=t[xy]):
        find(z.right,s,t,d,nums)

def add_Node(root,k,n):
    y = None
    x = root
    d = 0
    xy = 0
    while(x != None):
        d += 1
        xy = d%2
        y = x
        if x.key[xy] > k[xy]:
            x = x.left
        else:
            x = x.right
    
    z = Node(k,n)

    if y.key[xy] > k[xy]:
        y.left = z
    else:
        y.right = z
        
def recursive_add_Node(root,keys,depth):
    keys.sort(key=itemgetter(depth%2))
    id_m = len(keys)/2
    add_Node(root,keys[id_m][:2],keys[id_m][2])
   
    if id_m != 0:
        recursive_add_Node(root,keys[:id_m],depth+1)
    if id_m+1 != len(keys):
        recursive_add_Node(root,keys[id_m+1:],depth+1)

class Node():
    def __init__(self,k,n):
        self.key    = k
        self.num    = n
        self.left   = None
        self.right  = None
    


if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin,stdout
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline
 
def main():
    n = int(input())
    keys = map(lambda i: map(int,readline().split())+[i], xrange(n))
    keys.sort()

    root = int(math.sqrt(len(keys)))
 
    low = [x for x, y, i in keys[::root]]
    high = [x for x, y, i in keys[root - 1::root]] + [float('inf')]
 
    keys = [sorted(keys[i:i+root], key=itemgetter(1)) for i in range(0,len(keys),root)]
    keys_y = map(lambda k:[y for x,y,i in k], keys)

    q = int(input())
    for i in xrange(q):
        sx,tx,sy,ty = map(int,readline().split())
        
        nums = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            y = keys_y[i]
            for j in range(bisect_left(y, sy), bisect_right(y, ty)):
                if sx <= keys[i][j][0] <= tx:
                    nums.append(keys[i][j][2])
        if nums:
            nums.sort()
            map(lambda n:stdout.write("{}\n".format(n)), nums)
        print("")

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

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

freq = {}
a = [int(i) for i in input().split()]

for i in a:
    if i not in freq:
        freq[i] = 1
    else:
        freq[i] += 1

total = 0
while len(freq.keys()) > k:
    mn = (0,2000001)
    for i in freq.keys():
        if freq[i] < mn[1]:
            mn = (i,freq[i])
    total += mn[1]
    del freq[mn[0]]
print(total)


### FIXED CODE ###

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

freq = {}
a = [int(i) for i in input().split()]

for i in a:
    if i not in freq:
        freq[i] = 1
    else:
        freq[i] += 1
        
l = sorted(freq.values())
total = 0
index = 0

while len(l) - index > k:
    total += l[index]
    index += 1
print(total)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(S: str):
    N = len(S)
    U = [int(S[i:]) % 2019 for i in range(N)] + [0]
    table = [0]*2019

    tot = 0
    for i in range(N-1, -1, -1):
        tot += table[U[i]]
        table[U[i]] += 1
    tot += table[0]
    print(tot)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))  # type: str
    solve(S)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(S: str):
    N = len(S)
    U = [0]*(N+1)
    a = 0
    beki = 1
    for i in range(N-1, -1, -1):
        a += beki*(ord(S[i])-ord("0"))
        a %= 2019
        beki = (beki*10) % 2019
        U[i] = a
    table = [0]*2019

    tot = 0
    for i in range(N-1, -1, -1):
        tot += table[U[i]]
        table[U[i]] += 1
    tot += table[0]
    print(tot)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))  # type: str
    solve(S)


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

from queue import Queue
H, W = map(int, input().split())
is_visited = [[False for w in range(W)] for h in range(H)]
q = Queue()
for h in range(H):
    Ah = list(input())
    for w in range(W):
        if Ah[w] == '#':
            q.put((h, w, 0))
            is_visited[h][w] = True
ans = 0
lrud = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1]
]
while not q.empty():
    x, y, c = q.get()
    for dx, dy in lrud:
        nx = min(max(0, x+dx), H-1)
        ny = min(max(0, y+dy), W-1)
        if not is_visited[nx][ny]:
            q.put((nx, ny, c+1))
            is_visited[nx][ny] = True
    ans = c
print(ans)

### FIXED CODE ###

INF = 10**9
H, W = map(int, input().split())
A = [list(input()) for h in range(H)]
# (0, 0), (0, W-1), (H-1, 0), (H-1, W-1)
ans = [[INF for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            ans[h][w] = 0
        tmp = ans[h][w]+1
        if h < H-1:
            ans[h+1][w] = min(tmp, ans[h+1][w])
        if w < W-1:
            ans[h][w+1] = min(tmp, ans[h][w+1])
for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        tmp = ans[h][w]+1
        if h > 0:
            ans[h-1][w] = min(tmp, ans[h-1][w])
        if w > 0:
            ans[h][w-1] = min(tmp, ans[h][w-1])
# print(ans)
print(max([w for h in ans for w in h]))
### BUGGY CODE ###

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

def f(i):
    total = 0
    for j in range(N):
        if j % 2 == 0:
            total += A[(i + j) % N]
        else:
            total -= A[(i + j) % N]
    return total

B = (f(i) for i in range(N))

print(*B)

# A[0] = B[0] // 2 + B[1] // 2
# A[1] = B[1] // 2 + B[2] // 2
# A[2] = B[2] // 2 + B[3] // 2
# A[3] = B[3] // 2 + B[4] // 2
# A[4] = B[4] // 2 + B[0] // 2

# A[0] - A[1] = (B[0] - B[2]) // 2
# A[1] - A[2] = (B[1] - B[3]) // 2
# A[2] - A[3] = (B[2] - B[4]) // 2
# A[3] - A[4] = (B[3] - B[0]) // 2
# A[4] - A[0] - (B[4] - B[1]) // 2

# A[0] - A[1] + A[2] - A[3] + A[4] = B[0]
# A[1] - A[2] + A[3] - A[4] + A[0] = B[1]
# A[2] - A[3] + A[4] - A[0] + A[1] = B[2]
# A[3] - A[4] + A[0] - A[1] + A[2] = B[3]


### FIXED CODE ###

from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

@lru_cache(maxsize=N)
def f(i):
    if i >= 2:
        return f(i - 2) + 2 * A[i - 1] - 2 * A[i - 2]
    total = 0
    for j in range(N):
        if j % 2 == 0:
            total += A[(i + j) % N]
        else:
            total -= A[(i + j) % N]
    return total

B = (f(i) for i in range(N))

print(*B)
### BUGGY CODE ###

import heapq
n, m = map(int, input().split())
jobs = [[int(x) for x in input().split()] for _ in range(n)]
jobs = sorted(jobs, key=lambda x:x[0], reverse=True)
ans = 0
q = []

for i in range(m+1):
    tmp = reversed(jobs[:])
    for job in tmp:
        if job[0] <= i:
            heapq.heappush(q, -jobs.pop()[1])
        else:
            break
    if len(q) > 0:
        ans += -heapq.heappop(q)
print(ans)


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
jobs = [[int(x) for x in input().split()] for _ in range(n)]
jobs = sorted(jobs, key=lambda x:x[0], reverse=True)
r_jobs = list(reversed(jobs[:]))
ans = 0
q = []
cnt = 0
l = len(jobs)
for i in range(m+1):
    while cnt < l:
        if r_jobs[cnt][0] == i:
            heapq.heappush(q, -jobs.pop()[1])
            cnt += 1
        else:
            break

    if q:
        ans += -heapq.heappop(q)

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

N, K = map(int, input().split())
ans = N
x = abs(N - K)
while ans > x:
    ans = x
    x = abs(x - K)
else:
    print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
ans = N
a = ans // K
b = ans % K

if a > 0:
    ans = N - K * a
    a = ans // K
    b = ans % K

if a  == 0:
    if ans > abs(ans - K):
        print(abs(ans - K))
    else:
        print(ans)
### BUGGY CODE ###

def main():
    import sys
    import re
    input = sys.stdin.readline
    N,Q = list(map(int, input().split()))
    S = list(input())
    L = []
    for _ in range(Q):
        temp = list(map(int, input().split()))
        L.append(temp)
    I = []
    for j in range(Q):
        cnt = 0
        l,r = L[j]
        S_2 = ''.join(S[l-1:r])
        print(len(re.findall('AC', S_2)))
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    import re
    input = sys.stdin.readline
    N,Q = list(map(int, input().split()))
    S = list(input())
    L = []
    for _ in range(Q):
        temp = list(map(int, input().split()))
        L.append(temp)
    dp = [0] * N
    for i in range(1,N):
        if S[i] == "C" and S[i-1] == "A":
            dp[i] = dp[i-1] + 1
        else:
            dp[i] = dp[i-1]
    for j in range(Q):
        l,r = L[j]
        print(dp[r-1] - dp[l-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

s = input()[::-1]
rem = [[0 for i in range(13)] for _ in range(len(s)+1)]
rem[0][0] = 1
for i, st in enumerate(s):
    if st == '?':
        for j in range(10):
            next = j * 10 ** i
            for k in range(13):
                rem[i+1][(k+next)%13] += rem[i][k]
    else:
        next = int(st) * 10**i
        for j in range(13):
            rem[i+1][(j+next)%13] = rem[i][j]
print(rem[len(s)][5]%mod)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = sys.stdin.readline()
n = len(s)-1
now = [0] * 13
now[0] = 1
for i in range(n)[::-1]:
    prev = now[::]
    now = [0] * 13
    c = n - i - 1#桁
    m = pow(10,c,13)
    if s[i] == '?':
        for k in range(10):
            l = (m*k) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        k = int(s[i])
        l = (m*k) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]
    # print(now)
print(now[5])
### BUGGY CODE ###

import itertools

line=input()
n,k=map(int,line.split())
s=set(list(range(n+1)))
sums=list()
while k!=(n+2):
     koko=list()
     sub=list(itertools.combinations(s,k))
     #print(sub)
     for val in sub:
          soso=0
          for i in val:
               soso+=(i+(10**100))
          if soso not in sums:
               sums.append(soso)
          
               
          
     
     
     
     k+=1
print(len(sums))


### FIXED CODE ###

line=input()
n,k=map(int,line.split())
sums=0
while k!=(n+2):
     if k==1:
          mini=0
     if k>=2:
          mini=(((k)*(k-1))/2)#%((10**9)+7)
     maxi=( (((n+1)*(n)) - ((n+1-k)*(n-k)) )/2  )#%((10**9)+7)
     sums+=(maxi-mini+1)
     sums=sums%((10**9)+7)
     k+=1
print(int(sums))
### BUGGY CODE ###

n,m,*L=map(int,open(0).read().split())
con=[[] for _ in range(n)]
c=[True]*n
for s,t in zip(*[iter(L)]*2):
	con[s-1]+=[t-1]
	c[t-1]=False
for i in range(n):
	if c[i]:
		root=i
		break
q=[(None,root)]
ans=[0]*n
while q:
	bef,cur=q.pop(0)
	for nxt in con[cur]:
		if nxt==bef:
			pass
		ans[nxt]=cur+1
		q.append((cur,nxt))
print("\n".join(map(str,ans)))



### FIXED CODE ###

def topologicalSort(g: list, deg: list):
	ret = []
	q = []
	for i, d in enumerate(deg):
		if not d:
			ret.append(i)
			q.append(i)
	while q:
		cur = q.pop(0)
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				ret.append(nxt)
				q.append(nxt)
	return ret

def main():
	v, e, *L = map(int, open(0).read().split())
	g = [[] for _ in range(v)]
	rev = [[] for _ in range(v)]
	deg = [0] * v
	for s, t in zip(*[iter(L)] * 2):
		g[s - 1].append(t - 1)
		rev[t - 1].append(s - 1)
		deg[t - 1] += 1
	order = topologicalSort(g, deg)
	idx = [None] * v
	for i, o in enumerate(order):
		idx[o] = i
	ans = [0] * v
	for i in range(v):
		if rev[i]:
			ans[i] = max(rev[i], key=lambda x: idx[x]) + 1
	print("\n".join(map(str, ans)))

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

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

sum = 0
for i in range(N-1):
    for j in range(i+1, N):
        sum += A[i] * A[j]

const = 10 ** 9 + 7
print(sum % const)

### FIXED CODE ###

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

res = []
res.append(A[0])
for i in range(len(A)-1):
    res.append(res[i] + A[i+1])

sum = 0
for i in range(N-1):
    sum += A[i] * (res[N - 1] - res[i])

print(sum % (10**9+7))
### BUGGY CODE ###

def divisor(n):
    ret = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ret.append(i)
            if i*i != n:
                ret.append(n//i)
    return ret

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

    m = (10**6) + 1
    c = [0]*m
    for i in a:
        c[i] += 1

    ans = 0
    for i in a:
        if c[i] > 1:
            continue
        for j in divisor(i):
            if i == j:
                continue
            if c[j] > 0:
                break
        else:
            ans += 1
    print(ans)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

from collections import Counter

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    c = Counter(a)
    used = set()
    m = 10**6 + 1
    cnt = [0]*m
    ans = 0
    for ai in a:
        if c[ai]>1:
            if ai not in used:
                used.add(ai)
                for i in range(ai, m, ai):
                    cnt[i] += 1
        else:
            if cnt[ai] == 0:
                ans += 1
                for i in range(ai, m, ai):
                    cnt[i] += 1
    print(ans)

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

import math
import sys
sys.setrecursionlimit(100000)

n, k = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(n - 1)]
qs = [list(map(int, input().split())) for _ in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

ans = [0 for _ in range(n)]

def dfs(x, v, ans):
	ans[x] = ws[x] + v
	if len(ds[x]) > 0:
		for nxt in ds[x]:
			ans = dfs(nxt, ans[x], ans)
	return ans

ans = dfs(0, 0, ans)

#print(ws)
#print(ds)

for i in range(n):
	print(ans[i])


### FIXED CODE ###

n, k = list(map(int, input().split()))
ls = [list(map(int, input().split())) for _ in range(n - 1)]
qs = [list(map(int, input().split())) for _ in range(k)]

ws = [0 for _ in range(n)]
for q in qs:
	ws[q[0] - 1] += q[1]

ds = [[] for _ in range(n)]
for l in ls:
	ds[l[0] - 1].append(l[1] - 1)

for i in range(0, n):
	for x in ds[i]:
		ws[x] += ws[i]

for i in range(n):
	print(ws[i])
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
A = list()
q = deque()
for i in range(H):
    s = input()
    for j, c in enumerate(s):
        if c == '#':
            q.append((i, j, 0))
    A.append([c for c in s])

ans = 0
while len(q) > 0:
    i, j, x = q.popleft()
    A[i][j] = '#'
    ans = max(ans, x)
    if i > 0 and A[i - 1][j] == '.':
        q.append((i - 1, j, x + 1))
    if j > 0 and A[i][j - 1] == '.':
        q.append((i, j - 1, x + 1))
    if i < H - 1 and A[i + 1][j] == '.':
        q.append((i + 1, j, x + 1))
    if j < W - 1 and A[i][j + 1] == '.':
        q.append((i, j + 1, x + 1))
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(300000)
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


H, W = MI()
grid = [list(input()) for _ in range(H)]

seen = set()
q = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            q.append((i, j, 0))
            seen.add(i * W + j)
while len(q) > 0:
    h, w, d = q.popleft()
    for dh, dw in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        if 0 <= h + dh < H and 0 <= w + dw < W and (h + dh) * W + w + dw not in seen:
            q.append((h + dh, w + dw, d + 1))
            seen.add((h + dh) * W + w + dw)
print(d)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9+1]*n
    dp[0] = 0
    for i in range(n-1):
        for j in range(i+1, min(n, i+k+1)):
            if dp[i] + abs(h[i] - h[j]) < dp[j]:
                dp[j] = dp[i] + abs(h[i] - h[j])
    print(dp[n-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9+1]*n
    dp[0] = 0
    for i in range(1, n):
        buf = [dp[j] + abs(h[j]-h[i]) for j in range(max(i-k,0), i)]
        dp[i] = min(buf)
    print(dp[n-1])

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

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

for i in range(len(A)):
    ans.append(A.index(i+1)+1)
print(*ans)

### FIXED CODE ###

import numpy as np

N = input()
A = list(map(int, input().split()))
ans = np.argsort(A)
print(*np.array(ans)+1)
### BUGGY CODE ###

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

def binary_search(list, item):
    low = 0
    high = len(list) - 1
    
    while low <= high:
        if item > list[high]:
          return high+1
          break
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
          return mid
        elif guess > item:
          high = mid -1
          if list[mid-1] < item:
            return mid-1
            break
        elif guess < item:
          low = mid + 1
          if list[mid+1] > item:
            return mid+1
            break
        else:
          print('error')

    return 0


count = 0        
for i in range(n-1):
  for k in range(i+1,n-1):
    a,b =L[i],L[k]
    L_temp = L[k+1:]
    binary_search(L_temp, a+b)
    count = count + binary_search(L_temp, a+b)
    
print(count)


### FIXED CODE ###

import bisect
n=int(input()) 
L=list(map(int, input().split())) 
L.sort()

count = 0        
for i in range(n-2):
  a = L[i]
  for k in range(i+1,n-1):
    b = L[k]

    count += bisect.bisect_left(L, a + b) - k -1
print(count)
### BUGGY CODE ###

K=int(input())
def gcd(p,q):
    if p%q==0:
        return q
    return gcd(q,p%q)
S=0
for i in range(K):
    for j in range(K):
        for k in range(K):
            S+=gcd(i+1,gcd(j+1,k+1))
print(S)

### FIXED CODE ###

K=int(input())
def gcd(p,q):
    if p%q==0:
        return q
    return gcd(q,p%q)
S=0
for i in range(K):
    for j in range(K):
        for k in range(K):
            S+=gcd(i+1,gcd(j+1,k+1))
print(S)
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
visited=[[float('inf')]*w for i in range(h)]
ans,b,q=0,[],deque()
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      q.append([i,j])
      visited[i][j]=0
while q:
  x,y=q.popleft()
  for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
    newx,newy=x+i,y+j
    if 0<=newx<h and 0<=newy<w:
      if maze[newx][newy]!='#' and visited[newx][newy]==float('inf'):
        visited[newx][newy]=visited[x][y]+1
        q.append([newx,newy])
        ans=max(ans,visited[newx][newy])
print(ans)


### FIXED CODE ###

from collections import deque
def main():
  h,w=map(int,input().split())
  hw=h*w
  maze=[list(input()) for i in range(h)]
  visited=[[hw]*w for i in range(h)]
  ans,q=0,deque()
  for i in range(h):
    for j in range(w):
      if maze[i][j]=='#':
        q.append((i,j))
        visited[i][j]=0
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='#' and visited[newx][newy]==hw:
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

import sys
from collections import deque
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def is_cond(T, A, B, h):
    h_new = [0 for i in range(len(h))]
    for i in range(len(h)):
        h_new[i] = h[i] - B*T

    s = 0
    for i in range(len(h)):
        if h_new[i] > 0:
            s += h_new[i] / (A - B) + (0 if h_new[i] % (A - B) == 0 else 1)

    return s <= T

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, A, B] = [long(input_raw[0]), long(input_raw[1]), long(input_raw[2])]
    h = []
    for i in range(N):
        input_raw = read_func().strip().split()
        h.append(long(input_raw[0]))
    
    l = 0L
    r = max(h)/B + 1
    while(1):
        #print l r
        if abs(l - r) <= 1:
            print r
            break
        T = (l + r)/2
        if is_cond(T, A, B, h) == True:
            r = T
        else:
            l = T


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def is_cond(T, A, B, h):

    s = 0
    for i in range(len(h)):
        h_new = h[i] - B*T
        if h_new > 0:
            s += h_new / (A - B) + (0 if h_new % (A - B) == 0 else 1)

    return s <= T

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, A, B] = [long(input_raw[0]), long(input_raw[1]), long(input_raw[2])]
    h = []
    for i in range(N):
        input_raw = read_func().strip().split()
        h.append(long(input_raw[0]))
    
    l = 0L
    r = max(h)/B + 1
    while(1):
        #print l r
        if abs(l - r) <= 1:
            print r
            break
        T = (l + r)/2
        if is_cond(T, A, B, h) == True:
            r = T
        else:
            l = T


if __name__ == '__main__':
    main()