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

from collections import Counter

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

c=Counter(a)

def eratosthenes(lim):
  is_p=[1]*lim
  is_p[0]=1
  is_p[1]=1

  for i in a:
    if is_p[i]:
      for j in range(i*2,lim,i):
        is_p[j]=0

  return is_p

lim=10**6+5
is_p=eratosthenes(lim)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)

### FIXED CODE ###

from collections import Counter

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

is_p=[1 for i in range(10**6+1)]

for i in set(a):
  v=i
  if is_p[v]:
    for j in range(v+v,10**6+1,v):
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)
### BUGGY CODE ###

K,S=map(int,input().split())
ans = 0
for X in range(K+1):
  for Y in range(K+1):
    for Z in range(K+1):
      if X+Y+Z==S:
        ans += 1
    
print(ans)

### FIXED CODE ###

K,S=map(int,input().split())
ans = 0
for X in range(K+1):
  for Y in range(K+1):
    Z = S-X-Y   
    if 0<= Z <= K:
      ans += 1
    
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

from copy import copy
from fractions import gcd

def all_gcd(numbers):
    result = numbers[0]
    for v in numbers:
        result = gcd(result, v)
    return result

def main():
    n = int(input())
    a = list(map(int, input().split()))
    max_gcd = 0
    del_number = -1
    for i in range(n):
        b = copy(a)
        del b[i]
        bgcd = all_gcd(b)
        if max_gcd < bgcd:
            max_gcd = bgcd
            del_number = a[i]
    print(max_gcd)




if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
 
from fractions import gcd
 
def all_gcd(numbers):
    result = numbers[0]
    for v in numbers:
        result = gcd(result, v)
    return result
 
def main():
    n = int(input())
    a = list(map(int, input().split()))
    # x[i] = gcd 0 to i
    x = []
    for i in range(n):
        prev = 0 if i == 0 else x[i - 1]
        x.append(gcd(a[i], prev))
    # y[i] = gcd i to n
    y = [0] * n
    y[n-1] = a[n-1]
    for i in range(2, n + 1):
        y[n-i] = gcd(y[n-i+1], a[n-i])

    max_gcd = 0
    for i in range(n):
        if i == 0:
            now_gcd = y[1]
        elif i == n-1:
            now_gcd = x[n-2]
        else:
            now_gcd = gcd(x[i-1], y[i+1])
        if now_gcd > max_gcd:
            max_gcd = now_gcd
    print(max_gcd)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,m,q = map(int,input().split())

train = [[0 for i in range(n+1)] for j in range(n+1)]

for _ in range(m):
    l,r = map(int,input().split())
    for i in range(n+1):
        for j in range(n+1):
            if i<=l and j>=r:
                train[i][j] += 1

for _ in range(q):
    p,q = map(int,input().split())
    print(train[p][q])


### FIXED CODE ###

import itertools

n,m,q = map(int,input().split())

lr = [[0 for i in range(n)] for j in range(n)]
for _ in range(m):
    l,r = map(int,input().split())
    lr[l-1][r-1] += 1

acc_lr = []
for l in lr:
    acc_lr.append([0] + list(itertools.accumulate(l)))

for _ in range(q):
    l,r = map(int,input().split())
    ans = 0
    for ls in acc_lr[l-1:r]:
        ans += ls[r] - ls[l-1]
    print(ans)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N,M =LI()

AB=[LI() for i in range(M)]
X=[]
for ab in AB:
	if ab[0] == 1:
		X.append(ab[1])
for ab in AB:
	if ab[1] == N:
		if ab[0] in X:
			print("POSSIBLE")
			exit()
	
print("IMPOSSIBLE")

### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N,M =LI()
X,Y=[],[]
for i in range(M):
	a = LI()
	if a[0] == 1:
		X.append(a[1])
	if a[1] == N:
		Y.append(a[0])
X=set(X)
Y=set(Y)
for x in X:
	if x in Y:
		print("POSSIBLE")
		exit()
	

	
print("IMPOSSIBLE")
### BUGGY CODE ###

n, m = map(int, input().split())
ans = set(range(1, n + 1))
for _ in range(m):
    l, r = map(int, input().split())
    st = set(range(l, r + 1))
    ans &= st
print(len(ans))


### FIXED CODE ###

def solve2():
    n, m = map(int, input().split())
    L = 1
    R = n
    for _ in range(m):
        l, r = map(int, input().split())
        L = max(L, l)
        R = min(R, r)
    if L <= R:
        print(R - L + 1)
    else:
        print(0)
solve2()
### BUGGY CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(m):
    b, c = map(int, input().split())
    A += [c]*b

A.sort(reverse=True)

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 _ in range(m)]

a.sort()
bc.sort(reverse=True, key=lambda x: x[1])
j = 0
for i in range(m):
    while j < len(a) and bc[i][0] > 0:
        if a[j] < bc[i][1]:
            a[j] = bc[i][1]
            bc[i][0] -= 1
        j += 1
print(sum(a))
### BUGGY CODE ###

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

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

ans = 0
for l in range(1, N+1) :
    for r in range(l, N+1) :
        tas = S[r] - S[l-1]
        if tas % M == 0 :
            ans += 1

print(ans)



### FIXED CODE ###

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

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

cat = {}
for s in S :
    mod = s % M
    if mod in cat :
        cat[mod] += 1
    else :
        cat[mod] = 1

def comb(n, k) :
    p = 1
    d = 1
    for i in range(k) :
        p *= (n - i)
        d *=(i + 1)
    return p // d

ans = 0
for key, val in cat.items() :
    if val < 2 :
        continue
    ans += comb(val, 2)

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

n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    visit = A[:i ] + A[i + 1 :]
    visit = [0] + visit + [0]
    cost = [abs(visit[i] - visit[i - 1]) for i in range(1, len(visit))]
    print(sum(cost))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
plan = [0] + A + [0]
cost = sum([abs(plan[i] - plan[i - 1]) for i in range(1, len(plan))])

for i in range(1, n + 1):
    diff = (abs(plan[i - 1] - plan[i]) + abs(plan[i] - plan[i + 1])) - abs(plan[i - 1] - plan[i + 1])
    print(cost - diff)
### BUGGY CODE ###

n = int(input())
p_lst = [e for e in range(1,n+1)]
first, last = 1, n-1
res = (n-1)*(first+last)/2
print(int(res))

### FIXED CODE ###

n = int(input())
first, last = 1, n-1
res = (n-1)*n//2
print(int(res))
### BUGGY CODE ###

s=raw_input()
l=len(s)

str=""
i=0
LSUM=[0]
cnt=0
ans=0
while i<l:
	x=s[i]
	if x=="A":
		str+="A"
		i+=1
		cnt=LSUM[-1]+1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		str+="D"
		i+=2
		cnt=LSUM[-1]
		ans+=cnt
	else:
		str+="X"
		i+=1
		cnt=0
	LSUM.append( cnt )

LSUM=LSUM[1:]

ans=0
for i,x in enumerate(str):
	if x=="D":
		ans+=LSUM[i]

print ans

### FIXED CODE ###

s=raw_input()
l=len(s)

i=0
cnt=0
ans=0
while i<l:
	x=s[i]
	if x=="A":
		i+=1
		cnt+=1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		i+=2
		ans+=cnt
	else:
		i+=1
		cnt=0


print ans
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(v,s):
    global c
    seen[v]=True
    for nv in G[v]:
        if seen[nv]:
            if nv in s:
                c=True
            continue
        dfs(nv,s|{v})
    srted.append(v)
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(input())
A=[list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
P=setID()
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
c=False
seen=[False]*P
srted=[]
for i in range(P):
    if not seen[i]:
        dfs(i,set())
if c:
    print(-1)
    exit()
dp=[1]*P
for v in reversed(srted):
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))

### FIXED CODE ###

from collections import deque
def tsort():
    que=deque([i for i,c in enumerate(In) if c==0])
    l=[]
    while que:
        v=que.popleft()
        l.append(v)
        for nv in G[v]:
            In[nv]-=1
            if In[nv]==0:
                que.append(nv)
    if len(l)!=P:
        print(-1)
        exit()
    return l
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(input())
A=[list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
P=setID()
In=[0]*P
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
        In[A[i][j+1]]+=1
srted=tsort()
dp=[1]*P
for v in srted:
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))
### BUGGY CODE ###

N, M = [int(x) for x in input().split()]
PY_list = [[int(x)-1 for x in input().split()] for _ in range(M)]
lst = [[] for _ in range(N)] 
for P, Y in PY_list:
    lst[P].append(Y)
for l in lst:
    l.sort()
for p, y in PY_list:
    print('{:06}{:06}'.format(p+1, lst[p].index(y)+1))


### FIXED CODE ###

from bisect import bisect_left
N, M = [int(x) for x in input().split()]
PY_list = [[int(x)-1 for x in input().split()] for _ in range(M)]
lst = [[] for _ in range(N)] 
for P, Y in PY_list:
    lst[P].append(Y)
for l in lst:
    l.sort()
for p, y in PY_list:
    print('{:06}{:06}'.format(p+1, bisect_left(lst[p], y)+1))
### BUGGY CODE ###

def get_ac(n, q, s, lrli):

    ans = []
    for i in lrli:
        ans.append(s[i[0]-1:i[1]].count("AC"))

    return ans

def main():
    n, q = map(int, input().split())
    s = str(input())
    lrli = [list(map(int, input().split()))for i in range(q)]
    ans = get_ac(n, q, s, lrli)
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def get_ac(n, q, s, lrli):

    ans = []
    nli = [0]*(n+1)

    for i in range(1, n):
        if s[i] == "C" and s[i-1] == "A":
            nli[i+1] = nli[i] + 1
        else:
            nli[i+1] = nli[i]

    for i in lrli:
        ans.append(nli[i[1]]-nli[i[0]])

    return ans

def main():
    n, q = map(int, input().split())
    s = list(str(input()))
    lrli = [list(map(int, input().split()))for i in range(q)]
    ans = get_ac(n, q, s, lrli)
    for i in ans:
        print(i)

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

import operator
from functools import reduce


n = int(input())
a = list(map(int, input().split()))
ans = reduce(operator.mul, a)
print(-1 if ans > 10**18 else ans)


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)


main()
### BUGGY CODE ###

import sys
import numpy as np

# 公式解説を見てからやった
# 複数サイクルでき、1-K回移動可能
# N < 5000?多分、O(N * 2N)くらいで行けそうに見えるが。。。

def main(N,K,P,C):


	# 一度計算したサイクル情報を一応キャッシュしておく。。。
	# あんまり意味なさそう
	cycleIDs = np.full( N, -1, dtype=np.int64 )
	cycleInfs = []


	# print(P)

	ans = -1e19
	cycleID = 0

	for n in range(N):

		v = n
		currentCycleItemCnt = 0
		currentCycleTotal = 0

		if cycleIDs[v] != -1:
			currentCycleItemCnt, currentCycleTotal = cycleInfs[ cycleIDs[v] ]
			# print(currentCycleItemCnt, currentCycleTotal)
		else:
			while True:
				# 全頂点について、属するサイクルを計算する
				currentCycleItemCnt += 1
				currentCycleTotal += C[v]

				v = P[v]
				if v == n:
					# サイクル発見
					cycleInfs.append( (currentCycleItemCnt, currentCycleTotal) )
					cycleID += 1
					break

				# 一応、一度サイクルを計算した頂点については、
				# その頂点の属するサイクルの情報をメモっておく。。。
				cycleIDs[v] = cycleID

		procCnt = 0
		currentCycleSumTmp = 0

		while True:

			# 頂点vにコマが置かれた時の最高スコアを計算し、
			# これまでの最高スコアを上回ったら、これまでの最高スコアを更新する
			procCnt += 1
			currentCycleSumTmp += C[v]
			if K < procCnt:
				break

			cycleLoopCnt = 0
			if procCnt < K and 0 < currentCycleTotal:
				cycleLoopCnt = int(( K - procCnt ) // currentCycleItemCnt)

			# print("v=", v, "currentCycleSumTmp=", currentCycleSumTmp, procCnt)
			tmp = currentCycleSumTmp + cycleLoopCnt * currentCycleTotal
			ans = max( int(ans), int(tmp) )

			v = P[v]
			if v == n:
				# サイクル終了
				break

	print(int(ans))


if __name__ == "__main__":
	N,K = map(int,input().split())
	P = np.array( input().split(), np.int64 )
	P -= 1
	C = np.array( input().split(), np.int64 )

	main(N,K,P,C)
	#print(ans)




### FIXED CODE ###

# 公式解説を見てからやった
# 複数サイクルでき、1-K回移動可能
# N < 5000?多分、O(N * 2N)くらいで行けそうに見えるが。。。

if __name__ == "__main__":

	N,K = map(int,input().split())
	P = [ int(p)-1 for p in input().split() ]
	C = list(map(int,input().split()))

	# 一度計算したサイクル情報を一応キャッシュしておく。。。
	# あんまり意味なさそう
	cycleIDs = [ -1 for _ in range(N) ]
	cycleInfs = []


	# print(P)

	ans = -1e10
	cycleID = 0

	for n in range(N):

		v = n
		currentCycleItemCnt = 0
		currentCycleTotal = 0

		if cycleIDs[v] != -1:
			currentCycleItemCnt, currentCycleTotal = cycleInfs[ cycleIDs[v] ]
			# print(currentCycleItemCnt, currentCycleTotal)
		else:
			while True:
				# 全頂点について、属するサイクルを計算する
				currentCycleItemCnt += 1
				currentCycleTotal += C[v]

				v = P[v]
				if v == n:
					# サイクル発見
					cycleInfs.append( (currentCycleItemCnt, currentCycleTotal) )
					cycleID += 1
					break

				# 一応、一度サイクルを計算した頂点については、
				# その頂点の属するサイクルの情報をメモっておく。。。
				cycleIDs[v] = cycleID

		procCnt = 0
		currentCycleSumTmp = 0

		while True:

			# 頂点vにコマが置かれた時の最高スコアを計算し、
			# これまでの最高スコアを上回ったら、これまでの最高スコアを更新する
			procCnt += 1
			currentCycleSumTmp += C[v]
			if K < procCnt:
				break

			cycleLoopCnt = 0
			if procCnt < K and 0 < currentCycleTotal:
				cycleLoopCnt = ( K - procCnt ) // currentCycleItemCnt

			# print("v=", v, "currentCycleSumTmp=", currentCycleSumTmp, procCnt)
			tmp = currentCycleSumTmp + cycleLoopCnt * currentCycleTotal
			ans = max( ans, tmp )

			v = P[v]
			if v == n:
				# サイクル終了
				break

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

import math

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

C = list(set(A))
M = len(C)
t = []
anst = 0
for i in range(M):
  t.append(A.count(C[i]))
  temp = A.count(C[i])
  if temp >=2:
    anst += math.factorial(temp)/(math.factorial(temp-2)*2)

#print(t)
#print(anst)
#print(jisyo[1])
for i in range(N):
  #print(t[C.index(A[i])])
  print(int(anst-t[C.index(A[i])]+1))


### FIXED CODE ###

import math

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

C = list(set(A))
M = len(C)
t = []
anst = 0
dic = {}
for i in A:
  if not i in dic:
    dic[i] = 0
  dic[i] += 1

jisyo = {}
for i in range(M):
  temp = dic[C[i]]
  jisyo[C[i]] = temp
  #t.append(A.count(C[i]))
  if temp >=2:
    anst += temp*(temp-1)/2

#jisyo = dict(zip(C, t))
#print(jisyo)   
for i in range(N):
  #print(t[C.index(A[i])])
  print(int(anst-jisyo[A[i]]+1))
### BUGGY CODE ###

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

count = 0

for X in range(K + 1):
  for Y in range(K + 1):
    for Z in range(K + 1):
      if X + Y + Z == S:
        count += 1

print(count)

### FIXED CODE ###

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

count = 0

for X in range(K + 1):
  for Y in range(K + 1):
      if S - (X + Y) <= K and S - (X + Y) >= 0:
        count += 1

print(count)
### BUGGY CODE ###

def cut(squares):
    ret = []
    for s in squares:
        for i,r in enumerate(ret):
            if s[0] >= r[0] and s[1] >= r[1]:#replace
                ret[i] = s
                break
            if s[0] <= r[0] and s[1] <= r[1]:#remove
                break
        else:
            ret.append(s)#append
    return ret

def merge(left, buttom):
    ret = []
    for b in buttom:
        for l in left:
            w = min(b[0],l[0]+1)
            h = min(b[1]+1,l[1])
            ret+=[(w,h),(1,b[1]+1),(l[0]+1,1)]
    return ret

while True:
    H,W = map(int, raw_input().split())
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    DP = [[[(0,0)] for _ in xrange(W+1)] for _ in xrange(H+1)]    
    for x in xrange(W-1,-1,-1):
        for y in (y for y in xrange(H-1,-1,-1) if field[y][x] != "*"):
            DP[y][x] = cut(merge(DP[y][x+1],DP[y+1][x]))
    ans = 0
    for x in xrange(W):
        for y in xrange(H):
            if DP[y][x]:
                ans = max(ans,max(w*h for w,h in DP[y][x]))
    print ans
            

### FIXED CODE ###

def re_push(stack,num):#re_push and return max
    count = 0
    pre = num
    ma = 0
    while True:
        count += 1
        cur = stack.pop()
        if cur <= num:
            ma = max(ma,(count-1) * pre)
            stack += [cur]
            stack += [num]*(count-1)
            break
        if cur < pre:
            ma = max(ma,(count-1) * pre)
            stack += [cur]*count
            count = 0
        pre = cur
    return ma
            
while True:
    H,W = map(int, raw_input().split(" "))
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    table = [[0]*(W+1) for _ in xrange(H)]
    for y in xrange(H-1,-1,-1):
        for x in (x for x in xrange(W-1,-1,-1) if field[y][x] != "*"):
            table[y][x] = table[y][x+1] + 1
    ma = 0
    for x in xrange(W):
        stack = [0,table[0][x]]
        for y in xrange(1,H):
            if table[y-1][x] > table[y][x]:
                ma = max(ma, re_push(stack,table[y][x]))
            stack.append(table[y][x])
        ma = max(ma, re_push(stack,0))
    print ma
### BUGGY CODE ###

import itertools


def main():
    N = int(input())
    S = list(input())

    ans = 0
    for v in itertools.permutations(range(N), 3):
        if v[0] < v[1] < v[2]:
            if (v[2] - v[1]) != (v[1] - v[0]):
                if (S[v[0]] != S[v[1]]) and (S[v[1]] != S[v[2]]) and (S[v[0]] != S[v[2]]):
                    ans += 1
    print(ans)
    return 0

if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
import collections

def main():
    N = int(input())
    S = input()

    c = collections.Counter(S)
    c = c['R'] * c['G'] * c['B']

    count = 0
    for i in range(N):
        for j in range(i+1, N):
            k = 2*j-i
            if k < N:
                if (S[i] != S[j]) and (S[j] != S[k]) and (S[i] != S[k]):
                    count += 1

    print(c - count)

    return 0

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

from collections import deque
N=int(input())

lasts=deque([int(input())])
for _ in range(N-1):
    a=int(input())
    
    if a<=lasts[0]:
        lasts.appendleft(a)
    else:
        for i in range(len(lasts)-1, -1, -1):
            if lasts[i]<a:
                lasts[i]=a
                break

print(len(lasts))

### FIXED CODE ###

import bisect
from collections import deque
N=int(input())
a=[int(input()) for _ in range(N)]
d=deque()

for i in range(N):
    p=bisect.bisect_left(d, a[i])
    #print(a[i], p, d)
    if p==0:
        d.appendleft(a[i])
    else:
        d[p-1]=a[i]
print(len(d))
### BUGGY CODE ###

import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 225):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(input())
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    tmp = values[:I]
    print(sum(n - t in tmp for t in tmp))

### FIXED CODE ###

import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 224):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(input())
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    print(len([1 for v in values[:I] if primes[n-v]]))
### BUGGY CODE ###

import itertools
k,s=map(int,input().split())
count=0

nums=[i for i in range(k+1)]

for i in itertools.product(nums,repeat=3):
  if sum(i)==s:
    count+=1
print(count)



### FIXED CODE ###

k,s=map(int,input().split())
count=0

nums=[i for i in range(k+1)]

for i in range(len(nums)):
  for j in range(len(nums)):
    if 0 <= s-i-j <= k:
      count+=1
print(count)
### BUGGY CODE ###

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

p = list(map(int,input().split()))

y = 0
z = []

for i in range(n-k+1):
    x = 0
    for j in range(i,k+i):
        x += (1 + p[j])/2
    z.append(x)
    if x > y:
        y = x


print(y)


### FIXED CODE ###

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

p = list(map(int,input().split()))

a = 0

for i in range(k):
    a += p[i]

ans = a

for i in range(n-k):
    a -= p[i]
    a += p[i+k]
    if a > ans:
        ans = a

ans = (ans+k)/2

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

k=int(input())


cnt=0
if k>3:
    for i in range(3,k):
        for j in range(1,k):
            
                
            if i*j<k:
                cnt+=1
            else:
                break
print(cnt+k-1+((k-1)//2))

### FIXED CODE ###

k=int(input())


cnt=0
if k>6:
    for i in range(7,k):
        for j in range(1,k):
            
                
            if i*j<k:
                cnt+=1
            else:
                break
print(cnt+k-1+((k-1)//2)+((k-1)//3)+((k-1)//4)+((k-1)//5)+((k-1)//6))
### BUGGY CODE ###

import sys
import itertools
input = sys.stdin.readline

def func(x, nn):
    value = 0
    for i, j in itertools.combinations(range(nn), 2):
        value += x[i] ^ x[j]
    ans = value % (10 ** 9 + 7)
    return ans

def main():
    n = int(input())
    li = tuple(map(int, input().split()))
    print(func(li, n))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    t = arr & 1
    c1 = np.count_nonzero((arr & 1))
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1

print(s % mod)
### BUGGY CODE ###

N,X,Y=map(int,input().split())

X-=1
Y-=1

dist=[0]*(N+1)


for i in range(N):
    for j in range(N):
        dist[(min(abs(i-j),abs(i-Y)+abs(X-j)+1,abs(i-X)+abs(Y-j)+1))]+=1
for d in range(1,N):
    print(dist[d]//2)
    
    

### FIXED CODE ###

N,X,Y=map(int,input().split())

X-=1
Y-=1

dist=[0]*(N+1)


for i in range(N):
    for j in range(i+1,N):
        dist[(min(abs(i-j),abs(i-Y)+abs(X-j)+1,abs(i-X)+abs(Y-j)+1))]+=1
for d in range(1,N):
    print(dist[d])