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

# diverta 2019 Programming Contest: B – RGB Boxes
R, G, B, N = [int(i) for i in input().split()]

bingo = 0

for r in range(N + 1):
    if R * r > N:
        break
    for g in range(N + 1):
        b = (N - (R * r + G * g)) // B
        if b >= 0 and R * r + G * g + B * b == N:
            bingo += 1

print(bingo)

### FIXED CODE ###

# diverta 2019 Programming Contest: B – RGB Boxes
R, G, B, N = [int(i) for i in input().split()]

bingo = 0

for r in range(0, 3001):
    if R * r > N:
        break
    else:
        for g in range(0, 3001):
            b = (N -(R * r + G * g)) // B
            if b < 0:
                break
            elif R * r + G * g + B * b == N:
                bingo += 1

print(bingo)
### BUGGY CODE ###

import heapq

INF = 10**15
n = int(input())
dist_mat = [[INF]*n for _ in range(n)]
edges = [[] for _ in range(n)]
for i in range(n-1):
    a, b, c = map(int,input().split())
    a -= 1
    b -= 1
    dist_mat[a][b] = c
    dist_mat[b][a] = c
    edges[a].append(b)
    edges[b].append(a)
    dist_mat[i][i] = 0

q, k = map(int, input().split())
k -= 1

que = [(0, k)]
heapq.heapify(que)
costs = [INF]*n
costs[k] = 0
while len(que) > 0:
    dist, current = heapq.heappop(que)
    for edge in edges[current]:
        if costs[edge] > costs[current] + dist_mat[current][edge]:
            costs[edge] = costs[current] + dist_mat[current][edge]
            heapq.heappush(que, (costs[edge], edge))

res = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    res.append(costs[x]+costs[y])

for ans in res:
    print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

n = int(input())
edges = [[] for _ in range(n)]
costs = [-1]*n
def dfs(current):

    for nex, cost in edges[current]:
        if costs[nex] != -1:
            continue
        costs[nex] = costs[current] + cost
        dfs(nex)

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

q, k = map(int, input().split())
k -= 1
costs[k] = 0
dfs(k)

res = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    res.append(costs[x]+costs[y])

for ans in res:
    print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
Nj = N
while True:
    Ni = Nj
    Nj = abs(Ni - K)
    if K == 1 or Nj == K:
        print(0)
        break
    elif Nj > Ni:
        print(Ni)
        break
    else:
        continue


### FIXED CODE ###

n,k = map(int,input().split())
if n % k ==0:
    print(0)
else:
    l = [n]
    p = n//k
    c = n-(p*k)
    half = k//2
    while c > half:
        c = abs(c-k)
    l.append(c)
    print(min(l))
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
### ローリングハッシュ rolling hash
import random
# M = 10**9+7
# M = 1<<63 - 1
# M = 9007199254740997
M = 92709568269121

b = random.choice(range(1,M))
def rhash_list(s):
    l = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:i+2 for i,c in enumerate(l)}
    ans = 0
    v = 1
    l = [0]
    for item in s:
        ans += d[item]*v
        v *= b
        ans %= M
        v %= M
        l.append(ans)
    return l
l = rhash_list(s)
if len(set(s))==n:
    ans = 0
else:
    binv = pow(b,M-2,M)
    pows = [None]*(n+1)
    v = 1
    for j in range(n+1):
        pows[j] = v
        v *= binv
        v%= M
#         pow(binv,j,M)
    ans = 0
    from collections import defaultdict
    for i in range(n//2, 0, -1):
        d = defaultdict(list)
        for j in range(n-i+1):
            d[((l[j+i]-l[j])*pows[j])%M].append(j)
        for k,v in d.items():
            if v[0]+i<=v[-1]:
                ans = i
        if ans>0:
            break
print(ans)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
### ローリングハッシュ rolling hash
import random
# M = 10**9+7
# M = 1<<63 - 1
M = 92709568269121

b = random.choice(range(1,M))
def rhash_list(s):
    l = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:i+2 for i,c in enumerate(l)}
    ans = 0
    v = 1
    l = [0]
    for item in s:
        ans += d[item]*v
        v *= b
        ans %= M
        v %= M
        l.append(ans)
    return l
l = rhash_list(s)
if len(set(s))==n:
    ans = 0
else:
    binv = pow(b,M-2,M)
    pows = [None]*(n+1)
    v = 1
    for j in range(n+1):
        pows[j] = v
        v *= binv
        v %= M
#         pow(binv,j,M)
    ans = 0
    from collections import defaultdict
    for i in range(n//2, 0, -1):
        d = defaultdict(list)
        for j in range(n-i+1):
            d[((l[j+i]-l[j])*pows[j])%M].append(j)
        for v in d.values():
            if v[0]+i<=v[-1]:
                ans = i
        if ans>0:
            break
print(ans)
### BUGGY CODE ###

from itertools import chain


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    ab, cd = abcd[:2 * m], abcd[2 * m:]
    fr, br = [[] for _ in range(n + 1)], [[] for _ in range(n + 1)]
    for a, b in zip(*[iter(ab)] * 2):
        fr[a].append(b)
        fr[b].append(a)
    for c, d in zip(*[iter(cd)] * 2):
        br[c].append(d)
        br[d].append(c)

    g = [-1] * (n + 1)
    s = 0
    while s < n:
        s += 1
        if g[s] >= 0:
            continue
        t, tt = set([s]), set(fr[s])
        while tt and t != tt:
            t, tt = t.union(tt), tt.union(set(chain.from_iterable(
                fr[i] for i in tt.difference(t))))
        for _t in t:
            g[_t] = len(t - set([_t]) - set(fr[_t]) - set(br[_t]))
    return " ".join(map(str, g[1:]))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


### FIXED CODE ###

class UnionFind:

    def __init__(self, n):
        self.t = [-1] * (n + 1)

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    ab, cd = abcd[:2 * m], abcd[2 * m:]
    fr, br = [[] for _ in range(n + 1)], [[] for _ in range(n + 1)]
    uf = UnionFind(n)
    for a, b in zip(*[iter(ab)] * 2):
        fr[a].append(b)
        fr[b].append(a)
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        if v < 0:
            uf.t[i] = i
    mp = {k: i for i, k in enumerate(set(uf.t[1:]))}
    g = [[] for _ in enumerate(mp.keys())]
    for i in range(n + 1):
        if uf.t[i] > 0:
            g[mp[uf.t[i]]].append(i)
    for c, d in zip(*[iter(cd)] * 2):
        br[c].append(d)
        br[d].append(c)

    *fr, = map(len, fr)
    *g, = map(set, g)
    *gn, = map(len, g)
    return " ".join([
        str(gn[mp[uf.t[i]]] - 1 - fr[i] - sum(j in g[mp[uf.t[i]]]
                                              for j in br[i]))
        for i in range(1, n + 1)
    ])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
### BUGGY CODE ###

N=int(input())
p=list(map(int,input().split()))
a=0

for i in range(N):
  if all(p[i]<=p[j] for j in range(i+1)):
    a+=1
print(a)
  

### FIXED CODE ###

N=int(input())
p=list(map(int,input().split()))
a=0
b=p[0]
for i in range(N):
  if p[i]<=b:
    a+=1
    b=p[i]
  else:
    pass
print(a)
### BUGGY CODE ###

def main(): 


    card_cnt, gate_cnt = map(int, input().split())

    LR = set(range(1, 100000+1))

    for _ in range(gate_cnt):
        L, R = map(int, input().split())
        LR.intersection_update(range(L, R+1))
        if len(LR) == 0:
            break

    print(len(LR))


if __name__ == "__main__":
    main() 

### FIXED CODE ###

def main(): 


    card_cnt, gate_cnt = map(int, input().split())

    min_v, max_v = map(int, input().split())
    for _ in range(1, gate_cnt):
        L,R = map(int, input().split())
        min_v = max(min_v, L)
        max_v = min(max_v, R)
        if min_v > max_v:
            print(0)
            break
    else:
        print(len(range(min_v, max_v+1)))

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

N = int(input())
Ln = list(map(int,input().split(' ')))
Ln.sort(reverse=True)

count = 0

def binary_area_search(target_list: list, target_item: int) -> int:
    '''
    @params
    target_list: [1,3,5](ACC)
    target_item: 2

    @return
    return index
    '''
    low = 0
    high = len(target_list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = target_list[mid]
        if guess > target_item:
            if mid == 0:
                return 0
            if target_item > target_list[mid-1]:
                return mid 
            high = mid -1
        else:
            if mid == len(target_list) - 1:
                return None
            if target_list[mid+1] > target_item:
                return mid + 1 
            low = mid + 1
    return None

for a in range(N):
    a_l = Ln[a]
    '''
    N^2*logN
    '''
    for b in range(a+1, N):
        b_l = Ln[b]
        c_threshold = a_l - b_l
        c_list = Ln[b+1:N]
        c_list.reverse()
        c_idx = binary_area_search(c_list,c_threshold)
        if c_idx is not None:
            count += len(c_list) - c_idx
    '''
    N^2
    '''
    '''
    current_min = N-1
    b = a +1
    while b <= current_min:
        c_idx = current_min
        bc = Ln[b] + Ln[c_idx]
        if a_l < bc:
            count += (current_min - b)
            b += 1
            continue
        current_min -= 1
    '''
print(count)

### FIXED CODE ###

N = int(input())
Ln = list(map(int,input().split(' ')))
Ln.sort(reverse=True)

count = 0
for a in range(N):
    a_l = Ln[a]
    current_min = N-1
    b = a +1
    while b <= current_min:
        c_idx = current_min
        bc = Ln[b] + Ln[c_idx]
        if a_l < bc:
            count += (current_min - b)
            b += 1
            continue
        current_min -= 1
    '''
    for b in range(a+1, N):
        if b >= current_min:
            break
        for c in range(b+1,N):
            c_idx = current_min
            bc = Ln[b] + Ln[c_idx]
            if a_l < bc:
                count += (current_min - b)
                break
            current_min -= 1
    '''
print(count)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0

    for i in range(n):
        flg = True
        if i != 0 and i != n - 1:
            if a[i] in a[: i] or a[i] in a[i + 1:]:
                flg = False
        elif i == n - 1:
            if a[i] in a[: i]:
                flg = False
        else:
            if a[i] in a[i + 1:]:

                flg = False

        for j in range(i):
            if a[i] % a[j] == 0:
                flg = False
            if a[i] < a[j] * 2:
                break

        if flg:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))

c = Counter(a)
b = [k for k, v in c.items() if v == 1]
b.sort()
d = {b: i for i, b in enumerate(b)}

gg = [True] * len(b)
mx = 10 ** 6 + 1
for i in c.keys():
    for j in range(2 * i, mx, i):
        if j in d:
            gg[d[j]] = False

print(sum(gg))
### BUGGY CODE ###

n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists,reverse=True)
from collections import Counter
dic=dict(Counter(lists))

ans=0
howmuch=[[] for i in range(30)]
for num in lists:
    c=0
    while num%2==0:
        num=num//2
        c+=1
    howmuch[c].append(num)
for i in range(30):
    if len(howmuch[i])<=1:
        pass
    else:
        dic=dict(Counter(howmuch[i]))
        for some in howmuch[i]:
            for j in range(1,30):
                if 2**j-some in dic.keys() and dic[some]>0 and dic[2**j-some]>0:
                    if some!=2**(j-1):
                        m=min(dic[some],dic[2**j-some])
                        dic[some]-=m
                        dic[2**j-some]-=m
                        ans+=m
                    elif some==2**(j-1):
                        ans+=dic[some]//2
                        dic[some]=dic[some]%2

print(ans)    
    
    
  

### FIXED CODE ###


from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
ans = 0

D = defaultdict(int)
for x in A:
    D[x] += 1
A.sort(reverse=True)

for x in A:
    for i in range(1, 31):
        if D[x] > 0:
            if 2**i-x in D.keys() and D[2**i-x] > 0:
                if 2**(i-1) != x:
                    ans += 1
                    D[x] -= 1
                    D[2**i-x] -= 1
for i in range(31):
    ans += D[2**i]//2
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
ans = 0
for j in range(60):
    count = 0
    for i in range(len(a)):
        a[i], pre = divmod(a[i], 2)
        count += pre
    ans += count*(N-count)*2**j
    ans %= MOD
print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
ans = 0
for j in range(60):
    count = 0
    for i in range(len(a)):
        a[i], pre = divmod(a[i], 2)
        count += pre
    ans += count*(N-count)*2**j
    ans %= MOD
print(ans)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
l=[r,g,b,n]
R=n//r
G=n//g
B=n//b
count=0
l=[r,g,b]
m=min(l)
l.sort()
a=n//l[0]
b=n//l[1]
c=n//l[2]
for _a in range(a+1):
  for _b in range(b+1):
    for _c in range(c+1):
      if _a+_b+_c<=n//m:
        if l[0]*_a + l[1]*_b + l[2]*_c == n:
          count+=1
print(count)


### FIXED CODE ###

r,g,b,n=map(int,input().split())
l=[r,g,b,n]
count=0
for i in range(n+1):
  for j in range(n+1):
    if (n-(i*r+j*g))/b==int((n-(i*r+j*g))/b) and (n-(i*r+j*g))/b>=0:
      count+=1
print(count)
### BUGGY CODE ###

import numpy as np
N=int(input())
count=0
for i in range(N-1):
    count+=i+1
print(count)

### FIXED CODE ###

import numpy as np
N=int(input())
count=N*(N-1)//2
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in range(n)]
ab = [(x,y) for x,y in zip(a,b)]
from operator import itemgetter
ab = sorted(ab,key=itemgetter(0),reverse=True)
dp = [[-10**14]*(n+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
  for j in range(i+2):
    if j >= 1:
      dp[i+1][j] = max(dp[i][j]+ab[i][0]*abs(ab[i][1]-(n-1-(i-j))),dp[i][j-1]+ab[i][0]*abs(ab[i][1]+1-j))
    if j == 0:
      dp[i+1][0] = dp[i][0] + ab[i][0]*abs(ab[i][1]-(n-1-i))
print(max(dp[n]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in range(n)]
ab = [(x,y) for x,y in zip(a,b)]
from operator import itemgetter
ab = tuple(sorted(ab,key=itemgetter(0),reverse=True))
dp = [[-10**14]*(n+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
  for j in range(i+2):
    if j >= 1:
      dp[i+1][j] = max(dp[i][j]+ab[i][0]*abs(ab[i][1]-(n-1-(i-j))),dp[i][j-1]+ab[i][0]*abs(ab[i][1]+1-j))
    if j == 0:
      dp[i+1][0] = dp[i][0] + ab[i][0]*abs(ab[i][1]-(n-1-i))
print(max(dp[n]))
### BUGGY CODE ###

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

for i in range(n):
    mul *= a[i]

if(mul > 1000000000000000000):
    mul = -1

print(mul)

### FIXED CODE ###

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

if 0 in a:
    print(0)
    exit()

for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        ans = -1
        break

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

x,y=map(int,input().split())

def gg(a,b):
    for d in range(b,0,-1):
        #print(d)
        if a%d==0 and b%d==0:
            return d
if x>y:
    print(gg(x,y))
else:
    print(gg(y,x))



### FIXED CODE ###

x,y=map(int,input().split())

def gg(a,b):
    if a%b==0 and b%b==0:
        return b
    return gg(b,a%b)

if x>y:
    print(gg(x,y))
else:
    print(gg(y,x))
### BUGGY CODE ###

n, m = map(int, input().split())
am = [int(input()) for _ in range(m)]
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
    if i-1 not in am:
        dp[i] += dp[i-1]
    if i-2 not in am:
        dp[i] += dp[i-2]
    dp[i] %= mod
print(dp[n])


### FIXED CODE ###

n, m = map(int, input().split())
am = set([int(input()) for _ in range(m)])
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
for i in range(1, n+1):
    if i in am:
        continue
    dp[i] = dp[i-2] + dp[i-1] 
    dp[i] %= mod
print(dp[-1])
### BUGGY CODE ###

def boundary_find(array, limit):
    ceil = len(array) - 1 
    floor = 0
    while 1:
        center = (ceil + floor) // 2
        if array[center] <= limit:
            floor = center
        else:
            ceil = center
        if ceil - floor == 1:
            break
    return ceil

n, c, k = map(int, input().split())
tList = [int(input()) for _ in range(n)]
tList.sort()
count = 0
while 1:
    limit = tList[0] + k
    last = min(c, len(tList))
    if tList[last - 1] <= limit:
        mark = last
    else:
        mark = boundary_find(tList, limit)
    count += 1
    tList = tList[mark:]
    if tList == []:
        break
print(count)

### FIXED CODE ###

def boundary_find(array, limit):
    ceil = len(array) - 1 
    floor = 0
    while 1:
        center = (ceil + floor) // 2
        if array[center] <= limit:
            floor = center
        else:
            ceil = center
        if ceil - floor == 1:
            break
    return ceil

n, c, k = map(int, input().split())
tList = [int(input()) for _ in range(n)]
tList.sort()
count = 0
first = 0
while 1:
    limit = tList[first] + k
    last = min(first + c, n)
    if tList[last - 1] <= limit:
        mark = last
    else:
        mark = boundary_find(tList, limit)
    count += 1
    first = mark
    if first == n:
        break
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
INF = 2**30
N = int(input())
A = list(map(int, input().split()))
E = []
for i in range(N):
    E.append([])
for i in range(N-1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    E[u].append(v)
    E[v].append(u)

ans = [0] * N
dp = [INF] * (N+10)

def dfs(now, par):
    ng = -1
    ok = N+5
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if A[now] <= dp[mid]:
            ok = mid
        else:
            ng = mid
    memo = dp[ok]
    dp[ok] = A[now]

    ng1 = 0
    ok1 = N+5
    while ok1 - ng1 > 1 :
        mid = (ok1 + ng1) // 2
        if dp[mid] == INF:
            ok1 = mid
        else:
            ng1 = mid
    ans[now] = ok1

    for to in E[now]:
        if to == par:
            continue
        dfs(to, now)
    dp[ok] = memo


dfs(0, -1)

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


### FIXED CODE ###

import sys
import bisect
sys.setrecursionlimit(10**9)
INF = 2**30
N = int(input())
A = list(map(int, input().split()))
E = []
for i in range(N):
    E.append([])
for i in range(N-1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    E[u].append(v)
    E[v].append(u)

ans = [0] * N
dp = [INF] * N

def dfs(now, par, len):
    ok = bisect.bisect_left(dp, A[now])
    memo = dp[ok]
    dp[ok] = A[now]

    ok1 = bisect.bisect_left(dp, INF)
    ans[now] = ok1

    for to in E[now]:
        if to == par:
            continue
        dfs(to, now, len+1)
    dp[ok] = memo

dfs(0, -1, 0)

for i in range(N):
    print(ans[i])
### BUGGY CODE ###

from collections import defaultdict


N = int(input())
A = list(map(int, input().split())) 
MOD = 10**9 + 7
def gcd(a,b):
  x = max([a,b])
  y = min([a,b])
  while y:
    x, y = y, x % y
  return x

# x * y = lcm(x, y) // gcd(x, y)より
def lcm(x, y):
  return x * y // gcd(x, y)

l = 1
for a in A:
    l = lcm(l, a)

ans = 0
for i in range(N):
    ans += l // A[i]
    #ans %= MOD

print(ans%MOD)


"""
def primes(num):
    if num == 1:
        d = defaultdict(int)
        d[1] = 1
        return d

    i = 2
    d = defaultdict(int)
    while i * i <= num:
        while num % i == 0:
            num //= i
            d[i] += 1
        i += 1
    if num > 1:
        d[num] += 1

    return d

d = primes(A[0])

for a in A[1:]:
    tmp_d = primes(a)
    dk = set(d.keys())
    tmp_dk = set(tmp_d.keys())
    dk = dk | tmp_dk
    for k in dk:
        d[k] = max(d[k], tmp_d[k])

lcm = 1

for k in d.keys():
    lcm *= k**d[k] % MOD


ans = 0
for i in range(N):
    ans += (lcm // A[i])
    ans %= MOD

print(ans)
"""

### FIXED CODE ###

from fractions import gcd


def main():
        
    N = int(input())
    A = list(map(int, input().split())) 
    MOD = 10**9 + 7


    l = 1

    for a in A:
        l = l * a // gcd(l, a)


    ans = 0
    for a in A:
        ans += (l // a)
    ans %= MOD

    print(ans)


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

N = int(input())
nums = [int(input()) for _ in range(N)]
# i<jで、 AiとAjが同じ色で塗られている場合、Ai < Ajが成り立つ.
# その際に、色の最小数をだす。
LISES = [[nums[0]]]

for index, num in enumerate(nums):
    if index == 0:
        continue
    for LIS in LISES:
        if LIS[-1] < num:
            LIS.append(num)
            break
    else:
        LISES.append([num])
print(len(LISES))


### FIXED CODE ###

import bisect
from collections import deque
N = int(input())
nums = [int(input()) for _ in range(N)]
# i<jで、 AiとAjが同じ色で塗られている場合、Ai < Ajが成り立つ.
# その際に、色の最小数をだす。
LIS = deque([nums[0]])
count = 0
for index, num in enumerate(nums):
    if index == 0:
        continue
    if num <= LIS[0]:
        LIS.appendleft(num)
    else:
        insert_index = bisect.bisect_left(LIS, num)
        LIS[insert_index - 1] = num
print(len(LIS))
### BUGGY CODE ###

xx = []
n, k = map(int, input().split())
for i in range(n):
  a, b = map(int, input().split())
  for j in range(b):
    xx.append(a)
yy = sorted(xx)
print(yy[k-1])

### FIXED CODE ###

xx = []
n, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
xx = sorted(ab, key= lambda x:x[0])

ans = 0
for i in range(n):
  ans += xx[i][1]
  if ans >=  k:
    print(xx[i][0])
    break
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(N):
  x = i + 1
  ans = A.count(x)
  print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0] * N
for i in range(N - 1):
  x = A[i] - 1
  B[x] = B[x] + 1
for i in range(N):
  print(B[i])
### BUGGY CODE ###

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

graph=[]
for _ in range(N+1):
  graph.append([])

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  if t>300003:
    print(-1)
    sys.exit()
  
  nlist = []
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      table[v][t%3]=True
      for vv in graph[v]:
        if not table[vv][(t+1)%3]:
          nlist.append(vv)          
          #table[vv][t%3]=True
          #print((vv,t%3))
      
  #print((t,nlist))
  vlist = nlist
  if len(vlist) == 0:
    print(-1)
    break
  


### FIXED CODE ###

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

graph=[]
for _ in range(N+1):
  graph.append([])

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  #if t>300003:
  #  print(-1)
  #  sys.exit()
  
  #nlist = []
  nset = set()
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      table[v][t%3]=True
      for vv in graph[v]:
        if not table[vv][(t+1)%3]:
          #nlist.append(vv)
          nset.add(vv)
          #table[vv][t%3]=True
          #print((vv,t%3))
      
  #print((t,nlist))
  #vlist = nlist
  vlist = list(nset)
  if len(vlist) == 0:
    print(-1)
    break