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

N = int(input())
As = list(map(int, input().split(' ')))

not_divisible = 0
for num1, Ai in enumerate(As):
    for num2, Aj in enumerate(As):
        if num1==num2:
            continue
        if Ai%Aj == 0:
            break
    else:
        not_divisible += 1
print(not_divisible)

### FIXED CODE ###

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

max_a = max(a)
dp = [0] * (max_a + 1)

for i in a:
    for j in range(i, max_a+1, i):
        dp[j] += 1
        
print([dp[i] for i in a].count(1))
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
ls = [r,g,b]
z = ls[0]
y = ls[1]
x = ls[2]
ls.sort()
p = n
q = 0
X = n//x +1
Y = n//y +1
Z = n//z +1
for i in range(X):
    p = n
    for j in range(Y):
        p = n -i*x
        if p >= j*y:
            p = 0
        else:
            break
        for k in range(Z):
            p = n -i*x -j*y
            if p == k*z:
                q += 1
print(q)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
ans = 0
cnt = 0
for i in range(n//r+1):
    ans = 0
    for j in range((n-i*r)//g+1):
        ans = i*r+j*g
        a = (n-ans)/b
        if a % 1 == 0:
            cnt +=1
print(cnt)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
count = 0

import itertools
C = list(itertools.combinations(L,3))
l = len(C)

for i in range(l):
    if C[i][0] + C[i][1] <= C[i][2]:
        pass
    elif C[i][1] + C[i][2] <= C[i][0]:
        pass
    elif C[i][2] + C[i][0] <= C[i][1]:
        pass
    else:
        count = count + 1

print(count)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
C = sorted(L)
count = 0

import bisect
for i in range(N - 2):
    for  j in range(N - i - 2):
        s = C[i] + C[j + i + 1]
        t = bisect.bisect_left(C,s)
        u = t - (j + i + 1) - 1
        if u <= 0:
            pass
        else:
            count = count + u

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

import numpy as np

def main():
    n, k = map(int, input().split())
    hs = np.array(list(map(int, input().split())))

    dp = [float("inf")]*n
    dp[0] = 0

    for i in range(n):
        for j in range(1,k+1):
            if i+j < n:
                dp[i+j] = min(dp[i+j], dp[i]+abs(hs[i]-hs[i+j]))
    print(int(dp[-1]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

INF = 10**10

def main():
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))

    dp = [INF]*n
    dp[0] = 0

    for i in range(1,n):
        from_ = max(i-k, 0)
        dp[i] = min(d + abs(hs[i]-h) for d, h in zip(dp[from_:i], hs[from_:i]))
    print(dp[-1])

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

# n, lは最大100
# 計算量はn^2
# これであれば全探索いけるか
import itertools

(n, l) = map(int, input().split())
s = [input() for _ in range(n)]

candidates = []
index_candidates = list(itertools.permutations(range(len(s))))
for c in index_candidates:
  str = ""
  for index in c:
    str += s[index]
  candidates.append(str)

min_str = candidates[0]
for i in range(1, len(candidates)):
  for j in range(len(min_str)):
    if min_str[j] > candidates[i][j]:
      min_str = candidates[i]
      break
    elif min_str[j] < candidates[i][j]:
      break
print(min_str)

### FIXED CODE ###

(n, l) = map(int, input().split())
s = "".join(sorted([input() for _ in range(n)]))
print(s)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
if min(a) == 0:
    print(0)
else:
    for i in range(n):
        ans *= a[i]
        if ans > 10**18:
            ans = 0
    print(ans if ans != 0 else -1)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
z=list(map(int,input().split()))

L=[xx+yy for xx in x for yy in y ]
L=sorted(L,reverse=True)

if K > X*Y:
  LL=[l+zz for l in L for zz in z]
  [print(i) for i in sorted(LL,reverse=True)]   
else:
  LL=[l+zz for l in L[:K] for zz in z]
  LL=sorted(LL,reverse=True)
  [print(ll) for k,ll in zip(range(K),LL)]

### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
z=list(map(int,input().split()))

L=[xx+yy for xx in x for yy in y ]
L=sorted(L,reverse=True)

if K > X*Y:
  LL=[l+zz for l in L for zz in z]
  [print(i) for i in sorted(LL,reverse=True)]   
else:
  LL=[l+zz for l in L[:K] for zz in z]
  LL=sorted(LL,reverse=True)
  [print(ll) for k,ll in zip(range(K),LL)]
### BUGGY CODE ###

n = int(input())
x = 0
ans = -1
for i in range(1000000):
  x = x * 10 + 7;
  if x % n == 0:
    ans = i + 1
    break
print(ans)


### FIXED CODE ###

def solve(n):
  s = set()
  i = 1;
  x = 7 % n
  while (not (x in s)):
    if x == 0:
      return i;
    s.add(x)
    x = x * 10 + 7;
    x %= n;
    i += 1
  return -1

if __name__ == '__main__':
  n = int(input())
  if n == 2 or n == 5:
    print(-1)
  else:
    print(solve(n))
### BUGGY CODE ###

N, K = map(int, input().split(' '))
h = [None] + list(map(int, input().split(' ')))

dp = [None for _ in range(N+1)]
# dp[0], dp[1], ..., dp[N] が用意される

dp[1] = 0
for k in range(2, N+1): # k = 2, ..., N
  candidate = []
  for i in range(1, K+1): # i = 1, 2, ..., K
    if k - i <= 0:
      break
    candidate.append(dp[k-i] + abs(h[k] - h[k-i]))
  dp[k] = min(candidate)

print(dp[N])



### FIXED CODE ###

N, K = map(int, input().split(' '))
h = [None] + list(map(int, input().split(' ')))

dp = [None for _ in range(N+1)]
# dp[0], dp[1], ..., dp[N] が用意される

dp[1] = 0
for k in range(2, N+1): # k = 2, ..., N
  candidate = []
  for i in range(1, K+1): # i = 1, 2, ..., K
    if k - i <= 0:
      break
    candidate.append(dp[k-i] + abs(h[k] - h[k-i]))
  dp[k] = min(candidate)

print(dp[N])
### BUGGY CODE ###

import numpy as np
N,M = map(int, input().split())
A_B_list = [[int(i) for i in input().split()] for j in range(M)]
ans = np.zeros(N)
next_list = [1]
next_next_list = []
flag = False
while np.any(ans==0):
    for nxt in next_list:
        for ab in A_B_list: #1に繋がってるやつを消す
            if nxt == ab[0] and ans[ab[1]-1] == 0:
                ans[ab[1]-1] = nxt
                next_list.append(ab[1])
                
            elif nxt == ab[1] and ans[ab[0]-1] == 0:
                ans[ab[0]-1] = nxt
                next_list.append(ab[0])
                
    if len(next_list)==0:
        flag = True
        break
    next_list = next_next_list

if flag:
    print("No")
else:
    print("Yes")
    for i in ans[1:]:
        print(int(i))


### FIXED CODE ###

from collections import deque

n,m = map(int,input().split())
graph = [[] for _ in range(n)]
ans = [0] * n
for _ in range(m):
    a, b = map(int,input().split())
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a)


q = deque([0])
visited = [False] * n
visited[0] = True

while q:
    now = q.popleft()
    
    for i in graph[now]:
        if visited[i]: continue
        
        visited[i] = True
        ans[i] = now
        q.append(i)
        

print("Yes")
for a in ans[1:]:
    print(a+1)
### BUGGY CODE ###

n = int(input())

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

b = [0] * n
for i in range(n):
    b[i] = i + 1

d = dict(zip(a, b))

d_sorted = sorted(d.items(), key=lambda x:x[0])
ans = ""
for i in range(n):
    ans += str(d_sorted[i][1]) + " "

print(ans)

### FIXED CODE ###

n = int(input())

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

ans = [0] * n
for i in range(n):
    ans[a[i]-1] = i+1

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

n=int(input())
s=input()
rr=[]
gg=[]
bb=[]
for i in range(n):
  if s[i]=='R':
    rr.append(i)
  elif s[i]=='G':
    gg.append(i)
  else:
    bb.append(i)
lr=len(rr)
lg=len(gg)
lb=len(bb)
ans=lr*lg*lb
if ans==0:
  print(0)
  exit()
#print(ans,lr,lg,lb)
for x in rr:
  for y in gg:
    for z in bb:
      su=x+y+z
      xx,zz=min(x,y,z),max(x,y,z)
      yy=su-xx-zz
      if zz-yy==yy-xx:
        ans-=1




print(ans)

### FIXED CODE ###

n=int(input())
s=input()
rr=[]
gg=[]
bb=[]
for i in range(n):
  if s[i]=='R':
    rr.append(i)
  elif s[i]=='G':
    gg.append(i)
  else:
    bb.append(i)
lr=len(rr)
lg=len(gg)
lb=len(bb)
ans=lr*lg*lb
if ans==0:
  print(0)
  exit()
#print(ans,lr,lg,lb)
for xx in rr:
  for yy in gg:
    x,y=min(xx,yy),max(xx,yy)
    d=y-x
    a=x-d
    b=y+d
    if 0<=a<n and s[a]=='B':
      ans-=1
    if 0<=b<n and s[b]=='B':
      ans-=1
    if (x+y)%2==0:
      c=(x+y)//2
      if 0<=c<n and s[c]=='B':
        ans-=1



#print(rr,gg,bb)
print(ans)
### BUGGY CODE ###

import bisect

X, Y, Z, K = list(map(int, input().split()))
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
nums = []

for a in A:
    for b in B:
        for c in C:
            n = a + b + c
            idx = bisect.bisect_right(nums, n)
            if idx == 0 and len(nums) > K:
                break
            else:
                nums.insert(idx, n)
                if len(nums) > K:
                    nums.pop(0)
        if a + b + C[0] < nums[0]:
            break
    if a + B[0] + C[0] < nums[0]:
        break

for n in nums[::-1]:
    print(n)

### FIXED CODE ###

X, Y, Z, K = list(map(int, input().split()))
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

E = sorted([a+b for a in A for b in B], reverse=True)

E = E[:K]
nums = sorted([e+c for e in E for c in C], reverse=True)

for n in nums[:K]:
    print(n)
### BUGGY CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def input():
    return sys.stdin.readline().rstrip()


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    max_A = max(A)
    ans = 0
    best = 0
    for a in A:
        res = cmb(max_A, a)
        if best < res and max_A > a:
            best = res
            ans = a

    print(max_A, ans)


### FIXED CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    max_A = max(A)
    half_max_A = max_A / 2
    dist = [abs(half_max_A - a) for a in A]
    ans = 0
    best = 1000000005
    for i, d in enumerate(dist):
        if best > d and max_A > A[i]:
            best = d
            ans = A[i]

    print(max_A, ans)
### BUGGY CODE ###

div = 10**9 + 7
ans = 0

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

memo = {}

for i in range(N):
    for j in range(i+1,N):
        #print(str(i) + " : " + str(j))
        if (A[i],A[j]) in memo:
            ans += memo[A[i],A[j]]

        else:
            a = A[i]^A[j]
            memo[A[i],A[j]] = a
            ans+= a

#print(ans)
print(ans%div)


### FIXED CODE ###

div = 10**9 + 7
ans = 0

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

#最大値
A_max = max(A)
#最大値を２進数化
A_max_bin = format(A_max, 'b')
#その桁数
max_digits = len(A_max_bin)

#print(max_digits)

input_format = '0' + str(max_digits) + 'b'

A_bin = [ format(item,input_format) for item in A]

#print(A_bin)

ans = 0

for i in range(1,max_digits+1):
    num0 = 0
    num1 = 0
    #print("桁数 : " + str(i))
    for A_i in A_bin:

        #print(str(A_i) + " : " + str(A_i[-i]))
        #i桁目が0だったら

        #print(type(A_i[-1]))

        if A_i[-i] == '0':
            num0 += 1
        else:
            num1 += 1

    ans += num0 * num1 * 2**(i-1)
    #print(ans)

    num0 = 0
    num1 = 0

#print(ans)
print(ans%div)
### BUGGY CODE ###

N=int(input())

R=[[] for i in range(N)]

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

Q,K=map(int,input().split())
C=[0]*N
stack=[]
for i in range(N):
    if i==K-1:
        C[i]=0
    else:
        chk = [0] * N
        stack=[[K-1,i,0]]
        while stack:
            s,g,d=stack.pop()
            chk[s]=1
            for j,c in R[s]:
                if chk[j]==1:continue
                if j==g:
                    C[i]=d+c
                    break
                else:
                    stack.append([j,g,d+c])

for i in range(Q):
    x,y=map(int,input().split())
    print(C[x-1]+C[y-1])



### FIXED CODE ###

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

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

SD=[0]*N
seen=[0]*N
stack=[]
stack.append([K-1,0])
seen[K-1]=1
while stack:
    x,d=stack.pop()
    for y,d0 in G[x]:
        if seen[y]==0:
            SD[y]=d+d0
            stack.append([y,d+d0])
            seen[y]=1
for i in range(Q):
    x,y=map(int,input().split())
    ans=SD[x-1]+SD[y-1]
    print(ans)
### BUGGY CODE ###

import sys


n = int(input())

cost = sys.maxsize
tmp = 0

for i in range(1,n):
    if((n%i)==0):
        tmp = i + int(n/i) - 2
        cost = min(tmp,cost)
        tmp = 0

print(cost)


### FIXED CODE ###

import sys
import math

n = int(input())

cost = sys.maxsize
tmp = 0
k = math.sqrt(n)
for i in range(1,int(k)+1):
    q, mod = divmod(n,i)
    if(mod==0):
        tmp = i + int(q) - 2
        cost = min(tmp,cost)
        tmp = 0

print(cost)
### BUGGY CODE ###

n = int(input())
li_a = list(map(int, input().split()))
dic_a = {}

for a in li_a:
    dic_a[a] = dic_a.get(a, 0) + 1

q = int(input())
li_bc = list()

for i in range(q):
    li_bc.append(tuple(map(int, input().split())))

for l in li_bc:
    b = l[0]
    c = l[1]
    if b in dic_a.keys():
        dic_a[c] = dic_a.get(c, 0) + dic_a.get(b, 0)
        dic_a[b] = 0
    sum = 0
    for key, val in dic_a.items():
        sum += (key * val)
    print(sum)




### FIXED CODE ###

n = int(input())
li_a = list(map(int, input().split()))
dic_a = {}

for a in li_a:
    dic_a[a] = dic_a.get(a, 0) + 1

q = int(input())
li_bc = list()

for i in range(q):
    li_bc.append(tuple(map(int, input().split())))


answer = sum(li_a)
for l in li_bc:
    b = l[0]
    c = l[1]

    diff = (c - b) * dic_a.get(b, 0)
    if b in dic_a.keys():
        dic_a[c] = dic_a.get(c, 0) + dic_a.get(b, 0)
        dic_a[b] = 0
        answer += diff
    else:
        pass
    print(answer)
### BUGGY CODE ###

n=int(input())
temp=n+1
for i in range(1,n):
  if n%i==0 and temp>=i+n//i:
    temp=i+n//i
  elif n%i==0 and temp<i+n//i:
    break
print(temp-2)

### FIXED CODE ###

import math
n=int(input())
temp=n+1
for i in range(int(math.sqrt(n)),0,-1):
  if n%i==0:
    print(i+n//i-2)
    exit()
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
for i in range(n):
    print(max(a[:i]+a[i+1:]))

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
idx = a.index(max(a))
a.sort()
for i in range(n):
    if i==idx:
        print(a[-2])
    else:
        print(a[-1])
### BUGGY 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, m = na()
als = na()
ls = []
for i in range(m):
    b, c = na()
    ls.append([b, c])
ls.sort(key=lambda x: x[1], reverse=True)
while len(ls) > 0:
    m = min(als)
    if ls[0][0] == 0:
        ls.pop(0)
        if len(ls) == 0:
            break
    if m < ls[0][1]:
        als.remove(m)
        als.append(ls[0][1])
        ls[0][0] -= 1
    else:
        break
print(sum(als))


### FIXED CODE ###

import sys
from operator import itemgetter

stdin = sys.stdin

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


n, m = na()
a = na()
bcs = []
for i in range(m):
    bcs.append(na())
for i in range(n):
    bcs.append([1, a[i]])
bcs.sort(key=itemgetter(1))

ans = 0
rem = n
for i in range(m+n-1, -1, -1):
    use = min(rem, bcs[i][0])
    ans += use*bcs[i][1]
    rem -= use

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

import itertools
n = int(input())
a = list(map(int, input().split()))
idList = [i for i in range(1, n+1)]
'''
com = list(itertools.combinations(idList, 2))

num = len(com)
'''
ans = 0

for i in range(1, n + 1):
    for j in range(i + 2, n + 1):
        key = j - i
        heiA = a[i - 1]
        heiB = a[j - 1]
        height = heiA + heiB
        if (height == key):
            ans += 1

print(ans)
'''
for i in range(num):
    aa = com[i]
    # print(aa)
    idA = aa[0]
    idB = aa[1]
    dif = abs(idA - idB)
    indexA = idList.index(idA)
    indexB = idList.index(idB)

    height = a[indexA] + a[indexB]

    if (height == dif):
        ans += 1

print(ans)
'''


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

minus = [0] * N
plus = [0] * N

for i in range(N):
    minus[i] = (i + 1) - A[i]
    plus[i] = (i + 1) + A[i]

count = Counter(minus)
most = count.most_common()
num = len(most)

countPP = Counter(plus)
#mostPP = countPP.most_common()
#check = mostPP[:][0]
ans = 0

for i in range(num):
    elm = most[i]
    fir = elm[0]
    sec = elm[1]
    # if (fir in check):

    aa = countPP[fir]
    #    print(aa)
    ans += aa * sec

    # try countPP[tar]:

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

n, k = map(int, input().split())
h = [int(h) for h in map(int, input().split())]

for i in range(k):
	try:
		h.remove(max(h))
	except ValueError as e:
		pass
print(sum(h))

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(h) for h in map(int, input().split())]
if k >= len(h) and k > 0:
	print(0)
else:
	h.sort()
	print(sum(h[:n-k]))
### BUGGY CODE ###

# coding: utf-8
DATA = """
10 4 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N, X, Y = [int(i) for i in get_line().strip().split(" ")]
X-=1
Y-=1
INF = 10 **15
m = [[INF] * N for _ in range(N)]

ret = []
for i in range(N-1):
	m[i][i+1] = 1
	m[i+1][i] = 1
	ret.append((i, i+1))
ret.append((X, Y))
m[X][Y] = 1
m[Y][X] = 1

#print(ret)
#print(len(ret))

tt = [0] * N
for _ in range(N):
	tt2 = [0] * N
	for r in range(N):
		for c in range(r+1, N):
			if r == c:
				continue
			for k in range(N):
				m[r][c] = min(m[r][c], m[r][k] + m[k][c])
			#m[c][r] = m[r][c]
			if not m[c][r] == INF:
				tt2[m[r][c]] += 1
			m[c][r] = m[r][c]
	if tt2 == tt:
		break
	tt = tt2

# for i in m:
# 	print (i)

for t in tt[1:]:
	print (t)

### FIXED CODE ###

# coding: utf-8
DATA = """
10 4 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N, X, Y = [int(i) for i in get_line().strip().split(" ")]
X-=1
Y-=1
INF = 10 * 20
m = [[0] * N for _ in range(N)]
tt = [0] * N

#print(ret)
#print(len(ret))

for r in range(N):
	for c in range(r+1, N):
		m[r][c] = c - r
		#m[c][r] = m[r][c]
		tt[m[r][c]] += 1
		m[c][r] = m[r][c]

def Set(r, c, v):
	if m[r][c] < v:
		return False
	else:
		tt[m[r][c]] -= 1
		m[r][c] = v
		tt[m[r][c]] += 1
		return True

for r in range(N):
	if not Set(r, Y, m[r][X]+1):
		continue
	for c in range(Y+1, N):
		if not Set(r, c, m[r][c-1]+1):
			break
	for c in range(Y-1, X, -1):
		if not Set(r,c, m[r][c+1]+1):
			break

for t in tt[1:]:
	print (t)
### BUGGY CODE ###

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

for i in range(N):
    count = A.count(i+1)
    print(count)

### FIXED CODE ###

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

count = 0
buka = [0 for _ in range(N)]

for i in range(N-1):
    buka[A[i]-1] += 1

for k in range(N):
    print(buka[k])
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=[]
lstm=0
for i in range(N):
    flag=1
    for l in range(len(lst)):
        if lst[l]<A[i]:
            lst[l]=A[i]
            flag=0
            break
    if flag:
        lst.append(A[i])
        count+=1
    #print(count,i,lst)
print(count)


### FIXED CODE ###

import bisect
import collections

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=collections.deque([])
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if lst:
            lst.pop()
        else:
            count+=1
        continue
    idx=bisect.bisect_left(lst,A[i])-1
    #print(idx,lst,A[i])
    if idx<0:
        lst.appendleft(A[i])
        count+=1
    else:
        lst[idx]=A[i]

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

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

mini = float('inf')

for i in range(N):
    if abs(sum(A[0:i]) - sum(A[i:N])) < mini:
        mini = abs(sum(A[0:i]) - sum(A[i:N]))
    if abs(sum(A[0:-i]) - sum(A[-i:N])) < mini:
        mini = abs(sum(A[0:-i]) - sum(A[-i:N]))
    if mini == 0:
        break

print(mini)


### FIXED CODE ###

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

mini = float('inf')

cumsum = list(itertools.accumulate(A))
A.reverse()
rev = list(itertools.accumulate(A))
rev.reverse()
cumsum.pop()
rev.pop(0)

for i, j in zip(cumsum,rev):
    if abs(i-j) < mini:
        mini = abs(i-j)

print(mini)
### BUGGY CODE ###

N,Y=map(int,input().split())
for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            if i+j+k==N and 10000*i+5000*j+1000*k==Y:
                print("{} {} {}".format(i,j,k))
                exit()  
            
print("{} {} {}".format(-1,-1,-1))
  

### FIXED CODE ###

N,Y=map(int,input().split())
for i in range(N+1):
    for j in range(N-i+1):
        if 10000*i+5000*j+1000*(N-i-j)==Y:
                print("{} {} {}".format(i,j,N-i-j))
                exit()  
            
print("{} {} {}".format(-1,-1,-1))
### BUGGY CODE ###

s = input()
s = s.replace("BC", "X")
#"AX" -> "XA"
cnt = 0
while "AX" in s:
    cnt += s.count("AX")
    s = s.replace("AX", "XA")
print(cnt)

### FIXED CODE ###

#ABCがBCAになる
#ADがDAになる
s = input()
s = s.replace("BC", "D")

c_A = 0
ans = 0
for v in s:
  if v == "A":
    c_A += 1
  elif v == "D":
    ans += c_A
  else:
    c_A = 0
print(ans)
### BUGGY CODE ###

s=0
L=list()
N=int(input())
for i in range(N):
  S=sorted(list(input()))
  s+=L.count(S)
  L.append(S)
print(s)

### FIXED CODE ###

import collections
N=int(input())
j=0
L=list()
R=list()
for i in range(N):
  S="".join(sorted(list(input())))
  L.append(S)
c = collections.Counter(L)
counts=c.values()
counts=list(counts)
A=[i*(i-1)//2 for i in counts]
print(sum(A))