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

def main():
    n = int(input())
    A = sorted(map(int, input().split()), reverse=True)
    ans = 0
    mod = 10 ** 9 + 7
    m=A[0]
    for i in range(61):
        cnt0 = cnt1 = 0
        if m < 2 ** i:
            break
        for j, a in enumerate(A):
            if a < 2 ** i:
                cnt0 += n - j
                break
            if (a >> i) & 1:
                cnt1 += 1
            else:
                cnt0 += 1
        ans += (((2 ** i) % mod) * ((cnt1 * cnt0) % mod)) % mod
        ans %= mod

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    A = sorted(map(int, input().split()), reverse=True)
    ans = 0
    mod = 10 ** 9 + 7
    m=A[0]
    for i in range(61):
        cnt0 = cnt1 = 0
        if m < 2 ** i:
            break
        for j, a in enumerate(A):
            if a < 2 ** i:
                cnt0 += n - j
                break
            if (a >> i) & 1:
                cnt1 += 1
            else:
                cnt0 += 1
        ans += (((2 ** i) % mod) * ((cnt1 * cnt0) % mod)) % mod
        ans %= mod

    print(ans)

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

a,b,c,k=map(int,input().split())
wa=0
for i in range(k):
  if a>0:
    wa+=1
    a-=1
  else:
    if b>0:
      b-=1
    elif c>0:
      wa-=1
      c-=1
print(wa)


### FIXED CODE ###

a,b,c,k=map(int,input().split())
if k<=a:
  ans=k
elif k>a and k<=a+b:
  ans=a
else:
  ans=a-(k-(a+b))
print(ans)
### BUGGY CODE ###

# GCD
x, y = [int(i) for i in input().split()]

if x < y:
    buff = x
    x = y
    y = buff
elif x == y:
    print(x)
    exit()

r = x % y
for i in range(1, r+1):
    if y % i == 0 and r % i == 0:
        d = i

print(d)

### FIXED CODE ###

# GCD
def gcd(x, y):
    if x % y > 0:
        r = x % y
        d = gcd(y, r)
    else:
        d = y

    return d


x, y = [int(i) for i in input().split()]

if x < y:
    buff = x
    x = y
    y = buff
elif x == y:
    print(x)
    exit()

d = gcd(x, y)

print(d)
### BUGGY CODE ###

N,K=map(int,input().split())
S=input()

key=S[0]
cnt=1
count=[]
for i in range(1,N):
  if S[i]==key:
    cnt+=1
  else:
    count.append([key,cnt])
    key=S[i]
    cnt=1
count.append([key,cnt])

if len(count)==1:
  print(N)
  exit()

ans=0
for i in range(len(count)-1):
  if count[i][0]=="0":
    cnt=1
  else:
    cnt=0
  val=count[i][1]
  for j in range(i+1,len(count)):
    if count[j][0]=="0":
      val+=count[j][1]
      cnt+=1
      if cnt==K+1:
        val-=count[j][1]
        break
    else:
      val+=count[j][1]
  ans=max(ans,val)
print(ans)

### FIXED CODE ###

from itertools import accumulate

N,K=map(int,input().split())
S=input()

count=[0]
if S[0]=="0":
    count.append(0)

s=S[0]
cnt=0
for i in range(N):
    if s==S[i]:
        cnt+=1
    else:
        count.append(cnt)
        cnt=1
        s=S[i]
count.append(cnt)
if S[N-1]=="0":
    count.append(0)

l=len(count)
count=list(accumulate(count))
ans=0
for i in range(0,l,2):
    ans=max(ans,count[min(l-1,i+2*K+1)]-count[i])
print(ans)
### BUGGY CODE ###

s = input()
t = input()

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        # i番目以降の一致文字数
        while i + j < n and s[j] == s[i + j]:
            j += 1
        res[i] = j

        # 一文字も一致しない場合，次の文字へ
        if j == 0:
            i += 1
            continue

        # 一致したところまでを埋める
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        
        i += k
        j -= k
        
    return res


n = len(t)
ss = s
while len(ss) < n:
    ss += s
ss += s

z = z_algorithm(t + ss * 2)
z = [min(z[i], n) for i in range(n, len(z))]

ans = 0
for i in range(n):
    c = 0
    for v in z[i::n]:
        if v == n:
            c += 1
        else:
            c = 0
        ans = max(ans, c)
        
if ans <= len(ss) // n:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

s = input()
t = input()

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        # i番目以降の一致文字数
        while i + j < n and s[j] == s[i + j]:
            j += 1
        res[i] = j

        # 一文字も一致しない場合，次の文字へ
        if j == 0:
            i += 1
            continue

        # 一致したところまでを埋める
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        
        i += k
        j -= k
        
    return res


n = len(t)
if n > len(s):
    ss = s * (n // len(s) + 2)
else:
    ss = s * 2

z = z_algorithm(t + ss * 2)
z = [min(z[i], n) for i in range(n, len(z))]

ans = 0
for i in range(n):
    c = 0
    for v in z[i::n]:
        if v == n:
            c += 1
        else:
            c = 0
        ans = max(ans, c)
        
if ans <= len(ss) // n:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import math

def yo(n):
    if n==1:    return False
    s=2
    while s <= int(math.sqrt(n)):
        if n%s == 0:    return False
        s+=1
    return True

while True:
    c=0
    try:
        for i in range(1, int(input())+1):
            if yo(i)==True:    c+=1
        print(c)
    except:
        break

### FIXED CODE ###

def pri(s,n): 
    tab=[i for i in range(n+1) if s[i] and i>=2]
    return(tab)
 
s=[True for _ in range(999999+1)]
i=2
while i**2<=999999:
    if s[i]:
        j=i*2
        while j<=999999:
            s[j]=False
            j+=i
    i+=1

while True:
    try:
        print(len(pri(s,int(input()))))
    except:
        break
### BUGGY CODE ###


X, K, D = map(int, input().split())

flg = 0
minx = abs(X)
Xnow = X
Xprepre = 0
for i in range(K):
  if i != 0:
    Xprepre = Xpre
  Xpre = Xnow #前回
  X1 = Xnow -D
  X2 = Xnow +D
  if abs(X1) < abs(X2):
    Xnow = X1
  else:
    Xnow = X2
  #繰り返したらおわり
  if Xprepre == Xnow:
    flg = 1
    if (K-i+1)%2 == 0:
      print(abs(Xnow))
    else:
      print(abs(Xpre))
    break
if flg == 0:
  print(abs(Xnow))


### FIXED CODE ###


X, K, D = map(int, input().split())
K2 = K
#X=１に近いものにおきかえる
if X >= 0:
  a= 1
else:
  a = -1
#何回引けるか
h = min(K, int(a*X/D))
K = K-h
X = X - a*D*h

#print(X, K, D)
      


flg = 0
minx = abs(X)
Xnow = X
Xprepre = 0
for i in range(K):
  if i != 0:
    Xprepre = Xpre
  Xpre = Xnow #前回
  X1 = Xnow -D
  X2 = Xnow +D
  if abs(X1) < abs(X2):
    Xnow = X1
  else:
    Xnow = X2
  #繰り返したらおわり
  if Xprepre == Xnow:
    flg = 1
    if (K-i+1)%2 == 0:
      print(abs(Xnow))
    else:
      print(abs(Xpre))
    break
if flg == 0:
  print(abs(Xnow))
### BUGGY CODE ###

def solve():
    n = int(input())
    a = [0] * n
    indices = {}
    for i in range(n):
        a[i] = int(input())
        indices[a[i]] = i
    b = sorted(a)
    for j in range(n - 1, -1, -1):
        i = indices[b[j]]
        while i + 2 < n and a[i] > a[i + 2]:
            tmp = a[i + 2]
            a[i + 2] = a[i]
            a[i] = tmp
            indices[a[i]] = i
            indices[a[i + 2]] = i + 2
            i += 2
    ans = 0
    for i in range(n - 1):
        if a[i] != b[i]:
            ans += 1
            tmp = a[i + 1]
            a[i + 1] = a[i]
            a[i] = tmp
    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()


### FIXED CODE ###

def solve():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    e = [a[i] for i in range(0, n, 2)]
    a.sort()
    o = set(a[i] for i in range(1, n, 2))
    ans = 0
    for i in range((n + 1) // 2):
        if e[i] in o:
            ans += 1
    print(ans)


def main():
    solve()


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

N = int(input())
A = [int(input()) for i in range(N)]
for x in range(len(A)):
    a_copy = A[:]
    a_copy.pop(x)
    print(max(a_copy))


### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
maxA = max(A)
copy_A = A[:]
copy_A.remove(maxA)
secondA = max(copy_A)
for x in A:
    if x == maxA:
        print(secondA)
    else:
        print(maxA)
### BUGGY CODE ###

import functools
import math
import fractions

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

#gcd_all = functools.reduce(math.gcd, A)
gcd_all = functools.reduce(fractions.gcd, A)
#print(gcd_all)

for i in range(N):
    list = A[:i] + A[i+1:]
    #print(list)
    #gcd_1 = functools.reduce(math.gcd, list)
    gcd_1 = functools.reduce(fractions.gcd, list)
    #print(gcd_1)
    if gcd_1 >= gcd_all:
        #index = i
        #value = gcd_1
        gcd_all = gcd_1

#A[index] = value

#print(functools.reduce(math.gcd, A))
#print(functools.reduce(fractions.gcd, A))
print(gcd_all)


### FIXED CODE ###

from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))

L = [0] * (N+1)
R = [0] * (N+1)
for i in range(N):
    L[i+1] = gcd(L[i], A[i])
    R[N-i-1] = gcd(R[N-i], A[N-i-1])

max_m = 0
for i in range(N):
    m = gcd(L[i], R[i+1])
    if max_m < m:
        max_m = m
print(max_m)
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(1000000) 
N, K = list(map(int, input().split()))
H = list(map(int, input().split()))

def memoize(f):
    cache = {}
    def helper(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]
    return helper


@memoize
def jump(i):
    if i == 0:
        return 0
    mn = int(10 ** 9)
    for j in range(1, K + 1):
        if i - j >= 0:
            mn = min(mn, abs(H[i] - H[i - j]) + jump(i - j))
    return mn

print(jump(N - 1))




### FIXED CODE ###

import sys
import numpy as np

N, K = [int(v) for v in input().strip().split(' ')]

H = np.array([int(v) for v in sys.stdin.readline().strip().split(' ')])

dp = np.zeros(N, dtype=int)

for i in range(1, N):
    st = max(0, i - K)
    dp[i] = min(dp[st : i] + np.abs(H[i] - H[st : i]))

print(dp[-1])
### BUGGY CODE ###

S = list(map(int,input().split()))
N = S[0]
X = S[1]
x = list(map(int,input().split()))
n = max(max(x),X)//N 
x.append(X)
for i in range(n,0,-1):
    xmod = list(map(lambda y:y % i,x))
    if xmod.count(xmod[0]) == len(xmod):
        print(i)
        break

### FIXED CODE ###

import fractions
from functools import reduce

S = list(map(int,input().split()))
N = S[0]
X = S[1]
x = list(map(int,input().split()))
x.append(X)
xmin = min(x)
xlist = list(map(lambda y: y-xmin ,x))
xlist.remove(0)

answer = reduce(fractions.gcd, xlist)
print(answer)
### BUGGY CODE ###

N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))


### FIXED CODE ###

N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_cnt == 0:
        return 0
    if next_int == 0:
        return 1
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_cnt = X_cnt - 1
        if next_cnt == 0:
            next_int = 0
        else:
            next_int = f_m - pow(2, (N-i-1), next_cnt)  # マイナスでも正しく求まる？
    else:
        next_cnt = X_cnt + 1
        next_int = f_p + pow(2, (N-i-1), next_cnt)
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)
### BUGGY CODE ###

x=int (input())

i=0
c=100
d=100

while x >= d:
  c=int(c//100)
  d=d+c
  i=i+1



print(i)

### FIXED CODE ###

X=int(input())
total,Y=100,0
while X>total:
  total=total*101//100
  Y=Y+1
print(Y)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200005)

stdin = sys.stdin

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

n, q = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

ps = [0] * n
for i in range(q):
    p, x = na()
    p -= 1
    ps[p] += x

ans = [0] * n

def dfs(cur, pre, g, curv):
    global ps, ans
    curv += ps[cur]
    ans[cur] = curv
    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, curv)

dfs(0, -1, g, 0)

for x in ans:
    sys.stdout.write(str(x) + " ")


### FIXED CODE ###

import sys

stdin = sys.stdin

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

n, q = na()
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

ps = [0] * n
for i in range(q):
    p, x = na()
    p -= 1
    ps[p] += x

stack = [0] * (n+1)
inds = [0] * (n+1)

sp = 0
stack[sp] = 0
sp += 1

while sp > 0:
    cur = stack[sp-1]
    if inds[sp-1] == len(g[cur]):
        sp -= 1
        continue
    if inds[sp-1] == 0 and sp > 1:
        ps[cur] += ps[stack[sp-2]]
    if sp == 1 or stack[sp-2] != g[cur][inds[sp-1]]:
        stack[sp] = g[cur][inds[sp-1]]
        inds[sp] = 0
        inds[sp-1] += 1
        sp += 1
        continue
    inds[sp - 1] += 1

print(" ".join(map(str, ps)))
### BUGGY CODE ###

N = int(input())
ans = []
for n in range(1,N+1):
    result = 0
    for x in range(1,int(n**(1/2))+1):
        if x**2 < n:
            for y in range(1,int(n**(1/2))+1):
                if x**2+y**2 < n:
                    for z in range(1,int(n**(1/2))+1):
                        if x**2+y**2+z**2+x*y+y*z+z*x==n:
                            result += 1
    ans += [result]

print("\n".join(map(str,ans)))

### FIXED CODE ###

import itertools
N = int(input())
ans = [0 for i in range(0,N)]
for x, y, z in itertools.product(range(1,int(N**(1/2)+1)),range(1,int(N**(1/2)+1)),range(1,int(N**(1/2)+1))):
    kai = x**2+y**2+z**2+x*y+x*z+y*z
    if 0 < kai <= N:
        ans[kai-1] += 1

print("\n".join(map(str,ans)))
### BUGGY CODE ###

n,q = map( int, input().split() )
s = input()
lr = []
for i in range(q):
    lr.append(list( map( int, input().split() ) ) )

for i in range(q):
    cnt = 0
    for j in range(lr[i][0], lr[i][1]):
        if s[j-1:j+1] == 'AC':
            cnt += 1
    print(cnt)

### FIXED CODE ###

n,q = map( int, input().split() )
s = input()
lr = []
for i in range(q):
    lr.append(list( map( int, input().split() ) ) )

exist = [0]*n
for i in range(1,n):
    if s[i-1:i+1] == 'AC':
        exist[i] = exist[i-1]+1
    else:
        exist[i] = exist[i-1]

for i in range(q):
    print(exist[lr[i][1]-1]-exist[lr[i][0]-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()
a_list = []
for i in range(N):
    temp = _li_()
    temp.append(i-N)  # 番兵
    a_list.append(temp)
a_list = np.array(a_list)

n_index = np.arange(N)
a_index = np.zeros(N, dtype=int)
ans = 0

first = a_list[:, 0]
target = n_index[first[first] == n_index].tolist()
a_index[target] += 1
for i in range(N * (N-1) // 2):
    next_target = []
    for t in target:
        if t in next_target:
            continue
        cand = a_list[t, a_index[t]]
        if a_list[cand, a_index[cand]] == t:
            next_target.append(t)
            next_target.append(cand)

    target = next_target.copy()
    a_index[target] += 1
    ans += 1
    if len(target) == 0:
        break

if a_index.sum() == (N-1) * N:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

from sys import stdin
# import numpy as np
from collections import deque
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()

move_in = [[[] for i in range(N)] for j in range(N)]
move_out = [[[] for i in range(N)] for j in range(N)]
cost = [[0] * N for _ in range(N)]
start_pair = []
for i in range(N):
    a_list = _li_()
    start_pair.append(a_list[0])
    for j in range(N-2):
        start = [min(i, a_list[j]), max(i, a_list[j])]
        end = [min(i, a_list[j+1]), max(i, a_list[j+1])]
        move_in[end[0]][end[1]].append((start[0], start[1]))
        move_out[start[0]][start[1]].append((end[0], end[1]))

count = 0
stack = deque([])
for i in range(N):
    pair = start_pair[i]
    if i < pair and i == start_pair[pair]:
        stack.append((i, start_pair[i]))
        cost[i][start_pair[i]] = 1
        count += 1


ans = 0
while stack:
    cand = stack.pop()
    for dest in move_out[cand[0]][cand[1]]:
        cost[dest[0]][dest[1]] = max(cost[dest[0]][dest[1]],
                                     cost[cand[0]][cand[1]] + 1)
        in_list = move_in[dest[0]][dest[1]]
        if in_list[0] == cand:
            del in_list[0]
        else:
            del in_list[1]
        if len(in_list) == 0:
            count += 1
            if len(move_out[dest[0]][dest[1]]) == 0:
                ans = max(ans, cost[dest[0]][dest[1]])
            else:
                stack.append(dest)

if count == (N * (N-1) // 2):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import heapq
import sys

class rode():
    def __init__(self,x,y):
        self.x = x
        self.y = y
    def __lt__(self, other):
        return self.y < other.y
    def __gt__(self, other):
        return other > self
    def __le__(self, other):
        return not(other > self)
    def __ge__(self, other):
        return not(self > other)

n,m = map(int,input().split())
da = [[[i-1,0]] for i in range(n)]
da[0] = []
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
for i in range(1,n):
    da[i].append([i-1,0])
pq=[]
ju = [False for i in range(n)]
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, rode(i[0],i[1]))
while(len(pq)):
    now = heapq.heappop(pq)
    if now.x == n-1:
        print(now.y)
        sys.exit()
    if ju[now.x]:
        continue
    ju[now.x] = True
    for i in da[now.x]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,rode(i[0],now.y+i[1]))
print(-1)

### FIXED CODE ###

import heapq
import numpy as np
import sys

n,m = map(int,input().split())
da = [[] for i in range(n)]
for i in range(1,n):
    da[i].append([i-1,0])
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
pq=[]
ju = np.zeros(n,dtype=bool)
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, [i[1],i[0]])
while(len(pq)):
    now = heapq.heappop(pq)
    if now[1] == n-1:
        print(now[0])
        sys.exit()
    if ju[now[1]]:
        continue
    ju[now[1]] = True
    for i in da[now[1]]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,[now[0]+i[1],i[0]])
print(-1)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())
n, = map(int,readline().split())
vw = [(0,0)]+[tuple(map(int,readline().split())) for _ in range(n)]

#print(vw)
A = 9
N = min(1<<A,n+1)

memo = [None for _ in range(N)]
L = 10**5+1
memo[0] = [0]*L

for i in range(1,N):
    m = memo[i>>1][:]
    v,w = vw[i]    
    for j in range(L-1,w-1,-1):
        if m[j] < m[j-w]+v:
            m[j] = m[j-w]+v
    memo[i] = m
    #for j in range(1,L):
    #    memo[i][j] = max(memo[i][j],memo[i][j-1])


q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())
    
    ans = 0
    q = [(0,0,u)]
    while q:
        v,w,u = q.pop()
        if u < N:
            if w <= l:
                ans = max(ans,memo[u][l-w]+v)
        else:
            q.append((v,w,u>>1))
            q.append((v+vw[u][0],w+vw[u][1],u>>1))    

    print(ans)

        


### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#n,k,*a = map(int,read().split())

n, = map(int,readline().split())
vw = [[0,0]]+[list(map(int,readline().split())) for _ in range(n)]

def merge(av,aw,bv,bw):
    la,lb = len(aw),len(bw)
    rv = [0]*(la+lb)
    rw = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb or (ia < la and aw[ia] < bw[ib]):
            rv[i] = av[ia]
            rw[i] = aw[ia]
            ia += 1
        else:
            rv[i] = bv[ib]
            rw[i] = bw[ib]
            ib += 1
    return rv,rw

A = 10
N = min(1<<A,n+1)
memov = [[] for _ in range(N)]
memow = [[] for _ in range(N)]

memov[0] = [0]
memow[0] = [0]

#from itertools import acumulate
for i in range(1,N):
    v,w = vw[i]
    m2v = [v+v1 for v1 in memov[i>>1]]
    m2w = [w+w1 for w1 in memow[i>>1]]
    memov[i],memow[i] = merge(memov[i>>1],memow[i>>1],m2v,m2w)

    #memov[i] = list(accumulate(memov[i],max))
    for j in range(1,len(memov[i])):
        memov[i][j] = max(memov[i][j-1],memov[i][j])
    
def solve(lstv,lstw,dv,dw,l):
    ans = 0
    idx = len(lstw)-1
    #print(lstv,lstw,dv,dw,l)
    for v,w in zip(dv,dw):
        while idx >= 0 and lstw[idx] + w > l:
            idx -= 1
        if idx >= 0 and v+lstv[idx] > ans:
            ans = v+lstv[idx]
    print(ans)        
 
 

q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())

    dv = [0]
    dw = [0]
    while u >= N:
        v,w = vw[u]
        m2v = [v+v1 for v1 in dv]
        m2w = [w+w1 for w1 in dw]
        dv,dw = merge(dv,dw,m2v,m2w)
        u >>= 1
    
    #for j in range(1,len(dv)):
    #    dv[j] = max(dv[j-1],dv[j])
    
    solve(memov[u],memow[u],dv,dw,l)

#print(memov)
#print(memow)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
import bisect

def main():
    N = int(input())
    INF = 10**10
    col = [INF]
    for _ in range(N):
        num = int(input())
        ind = bisect.bisect_left(col,num)
        if ind == 0:
            col = [num]+col
        else:
            col[ind-1] = num
    
    print(len(col)-1)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
from collections import deque

def main():
    N = int(input())
    use = deque([int(input())])
    for _ in range(N-1):
        num = int(input())
        index = bisect.bisect_left(use,num)
        if index == 0:
            use.appendleft(num)
        else:
            use[index-1] = num
    
    print(len(use))
    
if __name__ == "__main__":
    main()