Harryxun/stf_run huggingface dataset:
import math


def main():
    import collections
    import numpy as np

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

    As = np.tile(A, (N, 1))

    for i, A in enumerate(As):
        # tmp_A = ignore(A, k)
        # tmp_A = [a in A: if ]
        A[i] = 0

        # tmp_A = collections.Counter(tmp_A)
        tmp_A = collections.Counter(A)
        su = 0
        for pairs in sorted(tmp_A.values(), reverse=True):
            if pairs >= 2:
                su += combinations_count(pairs, 2)
            else:
                break
        print(su)


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))




if __name__ == '__main__':
    main()


### FIXED CODE ###



def main():
    import collections

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

    allc = collections.Counter(A)
    # all_list = [0]*N
    allsu = 0
    for pairs in sorted(allc.values(), reverse=True):
        allsu += pairs*(pairs-1)//2

    for a in A:
        num = allc[a]
        print(allsu - (num-1))

    # for i in range(N):
    #     x = A[i]
    #     A[i] = 0
    #     tmp_A = cc(A)
    #     su = 0
    #     for pairs in sorted(tmp_A.values(), reverse=True):
    #         if pairs >= 2:
    #             su += pairs*(pairs-1)//2
    #         else:
    #             break
    #     A[i] = x
    #     print(su)


if __name__ == '__main__':
    main()
a , b = map(int,input().split())
k = []
for i in range(b):
    t,n = map(int,input().split())
    k.append(t)
    k.append(n)
    
import collections

v = collections.Counter(k)
for i in range(a):
    print (v.most_common()[i][1])

### FIXED CODE ###

a , b = map(int,input().split())
k = []
for i in range(b):
    t,n = map(int,input().split())
    k.append(t)
    k.append(n)
    
import collections

v = collections.Counter(k)
for i in range(a):
    print (v[i+1])
count = int(input())
if count == 0:
  result = 0
else:
  nums_str = input().split()
  nums_int = []
  for strn in nums_str:
    nums_int.append(int(strn))
 
    result = 1

    if 0 in nums_int:
      result = 0
    else:
      for intn in nums_int:
        result *= intn
        if result > 1000000000000000000:
          result = -1
          break
    
print(result)

### FIXED CODE ###

nums = input()
num1 = int(nums.split()[0])
num2 = int(nums.split()[1])

print(num1 * num2)
H, W = list(map(int, input().split()))
for i in range(H):
    C = input()
    print(C)
    print(C)



### FIXED CODE ###

text = input()
list1 = ['a','e','i','o','u']
if text in list1:
	print("vowel")
else:
	print("consonant")
n ,s = map(str,input().split())
if n[0]== s[2]and n[1]==s[1] and n[2]== s[0]:
    print('Yes')
else:
    print('No')

    

### FIXED CODE ###

n = str(input())
s = str(input())
if n[0]== s[2]and n[1]==s[1] and n[2]== s[0]:
    print('YES')
else:
    print('NO')
N, K = map(int, input().split())
S = input()

S[K-1] = S[K-1].lower()

print(S)


### FIXED CODE ###

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

S[K-1] = S[K-1].lower()

S = ''.join(S)
print(S)
from sys import stdin, stdout
from collections import deque, defaultdict
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	MOD = 10**9 + 7
	k, d = int(rl()), int(rl())
	ans = 0

	@lru_cache(None)
	def dfs(x, tight, i, tot):
		if i == len(x):
			return 1 if tot % d == 0 else 0
		start = 0 if i > 0 else 1
		maxdig = x[i] if tight else 9
		cnt = 0
		for dig in range(start, maxdig + 1):
			ntight = 1 if tight and dig == x[i] else 0
			cnt += dfs(x, ntight, i + 1, tot + dig)
		return cnt % MOD

	def totup(num):
		ans = deque()
		while num:
			num, dig = divmod(num, 10)
			ans.appendleft(dig)
		return tuple(ans)

	tupk = totup(k)
	ans += dfs(tupk, 1, 0, 0)
	for i in range(1, len(tupk)):
		bndry = 10**i-1
		ans += dfs(totup(bndry), 1, 0, 0)
		ans %= MOD

	print(ans % MOD)

	stdout.close()

if __name__ == "__main__":
	main()

### FIXED CODE ###

from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(100000)

def main():
	MOD = 10**9 + 7
	k, d = int(rl()), int(rl())
	ans = 0

	def totup(num):
		ans = deque()
		while num:
			num, dig = divmod(num, 10)
			ans.appendleft(dig)
		return tuple(ans)

	x = totup(k)

	dp = [[[0]*2 for j in range(d)] for i in range(len(x)+1)]
	dp[0][0][1] = 1
	for i in range(len(x)):
		for digsum in range(d):
			for tight in range(2):
				for dig in range(x[i]+1 if tight else 10):
					ns = (digsum + dig) % d 
					ntight = 1 if tight and dig == x[i] else 0
					dp[i+1][ns][ntight] += dp[i][digsum][tight]
					dp[i+1][ns][ntight] %= MOD

	ans = (dp[len(x)][0][0] + dp[len(x)][0][1] - 1) % MOD
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()
# -*- coding: utf-8 -*-

li = [int(input()) for i in range(5)]

li2 = list()

for i in li:
    if i % 10 != 0:
        i = (i // 10 + 1) * 10
    li2.append(i)

# li3 = [i for i in li if i % 10 != 0]

li4 = [int(str(i)[-1]) for i in li if i % 10 != 0]

# print(li3, li4)


print(sum(li2) - 10 + min(li4))

### FIXED CODE ###

# -*- coding: utf-8 -*-

li = [int(input()) for i in range(5)]

li2 = list()

for i in li:
    if i % 10 != 0:
        i = (i // 10 + 1) * 10
    li2.append(i)

# li3 = [i for i in li if i % 10 != 0]

li4 = [int(str(i)[-1]) for i in li if i % 10 != 0]

# print(li3, li4)

if not li4:
    print(sum(li))
else:
    print(sum(li2) - 10 + min(li4))
# 怪文書 / Dubious Document
n = int(input())
s=[]
for i in range(n):
    s.append(input())
ans = ""
ls = sorted(s[0])
for l in ls:
    if ( sum([l in s[i+1] for i in range(n-1)])//(n-1) ) :
        print(l)
        ans += l
        ls = ls[1:]
print(ans)        

### FIXED CODE ###

# 怪文書 / Dubious Document
n = int(input())
s=[]
for i in range(n):
    s.append(input())
ls = sorted(list(set(s[0])))
ans = ""
for l in ls:
    cnt = min ([s[i].count(l) for i in range(n)] )
    ans += l*cnt
print(ans)
s = input()
t = input()
ls = len(s)
lt = len(t)


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

            
if ls + lt == 0:
  print('')
else:
  
  i = ls-1
  j = lt-1
  while (0<=i & 0<=j):
      if s[i] == t[j]:
          answer += s[i]
          i -= 1
          j -= 1
      elif dp[i+1][j+1] == dp[i+1][j]:
          j -= 1
      else:
          i -= 1
  print(answer[::-1])


### FIXED CODE ###

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

dp=[0 for i in range(N)]
dp[1]=abs(H[1]-H[0])

for i in range(2,N):
    dp[i]=min(dp[i-1]+abs(H[i]-H[i-1]),dp[i-2]+abs(H[i]-H[i-2]))
print(dp[N-1])
n = input()
p = list(map(int, input().split()))
ans = 0
for i in p[2:]:
    if p[i] < p[i-1] < p[i-2] or p[i] > p[i-1] > p[i-2]:
        ans +=1
    else:
        continue
print(ans)


### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(1,n-1):
    if p[i+1] < p[i] < p[i-1] or p[i+1] > p[i] > p[i-1]:
        ans +=1
print(ans)
n = int(input())
a = list(map(int,input().split()))
s = 1

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

if s <= 10**18:
    print(s)
elif s > 10**18:
    print("-1")


### FIXED CODE ###

a,b = map(int,input().split())
print(a*b)
s = input()

if re.match('A?KIHA?BA?RA?$', s):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

import re

s = input()

if re.match('A?KIHA?BA?RA?$', s):
    print("YES")
else:
    print("NO")
k = int(input())
a, b = list(map(int, input().split()))
for i = range(a, b+1):
  if i % k == 0:
    print("OK")
    return
print("NO")


### FIXED CODE ###

k = int(input())
a, b = list(map(int, input().split()))
flg = False
for i in range(a, b+1):
  if i % k == 0:
    flg = True
    break
if flg:
  print("OK")
else:
  print("NG")
(n,m),*e=[[*map(int,i.split())]for i in open(0)]
d=[[]for i in range(n+1)]
for i,j in e:
    d[i]+=[j]
    d[j]+=[i]
print(max(len(set(d[i]+d[j]))for i in range(n+1)for j in d[i]))

### FIXED CODE ###

def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x == y:
        return 0
    if x<y:x,y=y,x    
    par[x]=y
n,m=map(int,input().split())
par=[i for i in range(n+1)]
for _ in range(m):
    i,j=map(int,input().split())
    unite(i,j)
ans=[0]*(n+1)
for i in range(n+1):
    find(i)
for i in par:
    ans[i]+=1
print(max(ans))
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    import numpy as np
    A.sort()
    ans = sum(A)
    from bisect import bisect_left,bisect_right
    from collections import Counter
    count = Counter(A)
    for i in range(q):
        b,c = map(int, input().split())
        k = count[b]
        if k != 0
            count[c] += count.pop(b)
        ans += (c-b)* k
        print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    import numpy as np
    A.sort()
    ans = sum(A)
    from bisect import bisect_left,bisect_right
    from collections import Counter
    count = Counter(A)
    for i in range(q):
        b,c = map(int, input().split())
        k = count[b]
        if k != 0:
            count[c] += count.pop(b)
        ans += (c-b)* k
        print(ans)


if __name__ == '__main__':
    main()
import sys #入力時間短縮
input = sys.stdin.readline

W,H=map(int,input().split())
p=sorted(int(input()) for i in range(W))
q=sorted(int(input()) for i in range(H))
ans=sum(p)*(H+1)+sum(q)*(W+1)
#1マスずつmax(pi,qj)→O(N^2)
#pi,qjが大きい順に列ごと消去→O(N)
for i in range(W+H-1):
  if p[len(p)-1]>=q[len(q)-1]:
    ans-=p[len(p)-1]*len(q)
    p.pop()
    if p==[]:
      print(ans)
      exit()
  else:
    ans-=q[len(q)-1]*len(p)
    q.pop()
    if q==[]:
      print(ans)
      exit()
  print(p,q)


### FIXED CODE ###

import sys
input = sys.stdin.readline

W,H=map(int,input().split())
p=sorted(int(input()) for i in range(W))
q=sorted(int(input()) for i in range(H))
ans=sum(p)*(H+1)+sum(q)*(W+1)
for i in range(W+H):
  if p[len(p)-1]>=q[len(q)-1]:
    ans-=p[len(p)-1]*len(q)
    p.pop()
    if p==[]:
      print(ans)
      exit()
  else:
    ans-=q[len(q)-1]*len(p)
    q.pop()
    if q==[]:
      print(ans)
      exit()
a,b = input()
print(b+a)

### FIXED CODE ###

s,t=input().split()
print(t+s)
import math
A, B = map(int, input().split())

print( (A*B)//math.gcd(A, B))

### FIXED CODE ###

import math

def computeGCD(x, y):
    if x > y:
        small = y
    else:
        small = x
    for i in range(1, small+1):
        if((x % i == 0) and (y % i == 0)):
            gcd = i
    return gcd
A, B = map(int, input().split())

print( (A*B)//computeGCD(A, B))
A, B = map(int, input().split())
count = B - A

if(count > 0):
  if count//(A-1) == 0:
	print(1 + count//(A-1))
  else:
    print(2 + count//(A-1))
else:
	print(1)


### FIXED CODE ###

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

print(math.ceil((B-1)/(A-1)))
string = input()
nums = [int(v) for v in string]
length = len(string) - 1
k = int(string)
d = int(input())

if length < 5:
    raise Exception()


### FIXED CODE ###

string = input()
d = int(input())

nums = [int(v) for v in string]
length = len(string) - 1
k = int(string)

M = 10**9 + 7
def mod(v):
    if v >= M:
        return v % M
    return v

dp = [[[None] * 2 for _ in range(d)] for _ in range(length + 2)]
def dfs(i=0, s=0, border=True):
    if dp[i][s][border] is not None:
        return dp[i][s][border]

    if i > length:
        r = int(not bool(s))
        dp[i][s][border] = r
        return r

    cnt = 0
    for n in range(max(9 * (not border), nums[i]) + 1):
        cnt = mod(cnt + dfs(i + 1, (s + n) % d, border and nums[i] == n))
    dp[i][s][border] = cnt
    return cnt
# print(mod(dfs() - 1))

for i in reversed(range(length + 2)):
    for s in reversed(range(d)):
        for border in [False, True]:
            if i > length:
                dp[i][s][border] = int(not bool(s))
                continue

            cnt = 0
            for n in range(max(9 * (not border), nums[i]) + 1):
                cnt = mod(cnt + dp[i + 1][(s + n) % d][border and nums[i] == n])
            dp[i][s][border] = cnt

print(mod(dp[0][0][1] - 1 + M))
from sys import stdin
from itertools import groupby

n,q = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n-1)]
lin = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]

kazu = [[]for _ in range(n)]
point = [0]*n

for i in range(len(li)):
    kazu[li[i][0]-1].append(li[i][1]-1)
    kazu[li[i][1]-1].append(li[i][0]-1)
for i in range(q):
    point[lin[i][0]-1] += lin[i][1]

def dfs(li,li2,now,before):
    for i in (li[now]):
        if i == before:
            continue
        li2[i] += li2[now]
        dfs(kazu,point,i,now)
dfs(kazu,point,0,-1)
print(*point)

### FIXED CODE ###

from sys import stdin
import sys
from itertools import groupby
sys.setrecursionlimit(10**6) 
n,q = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n-1)]
lin = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]

kazu = [[]for _ in range(n)]
point = [0]*n

for i in range(len(li)):
    kazu[li[i][0]-1].append(li[i][1]-1)
    kazu[li[i][1]-1].append(li[i][0]-1)
for i in range(q):
    point[lin[i][0]-1] += lin[i][1]

def dfs(li,li2,now,before):
    for i in (li[now]):
        if i == before:
            continue
        li2[i] += li2[now]
        dfs(kazu,point,i,now)
dfs(kazu,point,0,-1)
print(*point)
def resolve():
    N, M = map(int, input().split())
    d = Counter(list(map(int, input().split())))

    for i in range(M):
        b, c = map(int, input().split())
        d[c] += b

    d = dict(sorted(d.items(), reverse=True))

    def main():
        cnt = 0
        ans = 0

        for k, v in d.items():
            if cnt + v < N:
                ans += v * k
                cnt += v
            else:
                ans += (N - cnt) * k
                return ans

    print(main())



resolve()

### FIXED CODE ###

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

for _ in range(M):
  B, C = map(int, input().split())
  A[C] += B

A = sorted(A.items(), key=lambda x:x[0], reverse=True)

ans = 0
for key, count in A:
  if N > count:
    ans += key * count
    N -= count
  else:
    ans += key * N
    break

print(ans)
a,b = int(input().split())
print(max(a + b, a*2 - 1, b*2 - 1))

### FIXED CODE ###

a,b =map(int,input().split())
print(max(a + b, a*2 - 1, b*2 - 1))
n = input()
S = map(int, raw_input().split())
q = input()
T = map(int, raw_input().split())

count = 0

for i in range(n):
    Search = T[i]
    for j in range(q):
        if S[j] == Search:
            count = count + 1
            break

print count

### FIXED CODE ###

n = input()
S = map(int, raw_input().split())
q = input()
T = map(int, raw_input().split())

count = 0

for i in range(q):
    Search = T[i]
    for j in range(n):
        if S[j] == Search:
            count = count + 1
            break

print count
posX,posY=0,0
H,W=map(int,input())
for i in range(H):
    spam=input().rstrip()
    for j in range(W):
        if posX==j:
            if spam[j]=='>': posX+=1
            elif spam[j]=='<': posX-=1
            elif spam[j]=='v': posY+=1
            elif spam[j]=='^': posY-=1
        else: break

### FIXED CODE ###

H,W=1,1
while True:
    posX,posY=0,0
    H,W=map(int,input().split())
    if (H==W==0)==True:
        break
    tile=[[False for i in range(W)] for j in range(H)]
    tileinfo=[['' for i in range(W)] for j in range(H)]
    for i in range(H):
        tileinfo[i]=input().rstrip()
    while True:
        if tile[posY][posX]==True:
            print('LOOP')
            break
        else:
            tile[posY][posX]=True
        if tileinfo[posY][posX]=='>':
            posX+=1
        elif tileinfo[posY][posX]=='<':
            posX-=1
        elif tileinfo[posY][posX]=='v':
            posY+=1
        elif tileinfo[posY][posX]=='^':
            posY-=1
        elif tileinfo[posY][posX]=='.':
            print('{} {}'.format(posX,posY))
            break
A=int(input())
B=int(input())
C=int(input())
X=int(input())
n=0
for i in range(A+1):
    for j in range(B+1):
        if 0 <= (X-500*i-100*j)//50 <= C:
            n+=1
print(n)

### FIXED CODE ###

print((int(input())-int(input()))%int(input()))
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)

### 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)
N = input()

if N % 2 == 0:
  unpo = N / 2
  print(unpo)
else:
  unpo = (N / 2) + 1
  print(unpo)
  

### FIXED CODE ###

UNKO = int(input())
print(UNKO // 2 + UNKO % 2)
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;

  if (n>=2 && m>=2) {
      cout << n*m - (n-2)*2 - (m-2)*2 - 4 << endl;
  }
  else if (n==1 && m==1) {
      cout << 1 << endl;
  }
  else if (n==1 && m>=2) {
      cout << m-2 << endl;
  }
  else {
      cout << n-2 << endl;
  }
}

### FIXED CODE ###

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

if n>=2 and m>=2:
    print(n*m - (n-2)*2 - (m-2)*2 - 4)
elif n==1 and m==1:
    print(1)
elif n==1 and m>=2:
    print(m-2)
else:
    print(n-2)
import math
r = int(input())
ans = 2*r*pimath.pi
print(ans)

### FIXED CODE ###

import math
r = int(input())
ans = 2*r*math.pi
print(ans)
x,y = map(int,input().split())

if y<x<0 or 0<y<x:
    print(abs(x-y)+2)
elif (y<x and x=0) or (y=0 and y<x):
    print(abs(x-y)+1)
elif x<=y<=0 or 0<=x<=y:
    print(abs(x-y))
elif x<0<y or y<0<x:
    print(abs(abs(x)-abs(y))+1)

### FIXED CODE ###

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

if y<x<0 or 0<y<x:
    print(abs(x-y)+2)
elif (y<x and x==0) or (y==0 and y<x):
    print(abs(x-y)+1)
elif x<=y<=0 or 0<=x<=y:
    print(abs(x-y))
elif x<0<y or y<0<x:
    print(abs(abs(x)-abs(y))+1)
import itertools

def resolve():
    n, m = map(int, input().split())
    S = [[0]*m for i in range(m)]
    MOD = (10 ** 9) + 7

    for i in range(m):
        a, b = map(int, input().split())
        S[a-1][b-1] = 1
        S[b-1][a-1] = 1

    ans = 0
    for p in itertools.permutations(range(0, m)):
        if p == (0,2,3,4,5,6,1):
            pass
        if p[0] != 0:
            break;
        tmp = 1
        for i, v in enumerate(p):
            if i + 1 < m:
                tmp *= S[v][p[i+1]]
            if tmp == 0:
                break;
        ans += tmp

    print(ans % MOD)

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

# サンプルコード計算量お試し

import itertools

N, M = map(int, input().split())
adj_matrix = [[0]* N for _ in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    adj_matrix[a-1][b-1] = 1
    adj_matrix[b-1][a-1] = 1

cnt = 0

for each in itertools.permutations(range(N)):
    if each[0] != 0:
        break
    factor = 1
    for i in range(N-1):
        factor *= adj_matrix[each[i]][each[i+1]]
    cnt += factor

print(cnt)
import math

n = int(input())

for i in range(0, n) :
    a = int(input())
    b = int(input())
    if math.log10(a + b) + 1 > 80 :
        print("overflow")
    elif math.log10(a) + 1 > 80 :
        print("overflow")
    elif math.log10(b) + 1 > 80 :
        print("overflow")
    else :
        print(a + b)

### FIXED CODE ###

n = int(input())

for i in range(0, n):
    a = int(input())
    b = int(input())
    if len(str(a + b)) > 80:
        print("overflow")
    elif len(str(a)) > 80:
        print("overflow")
    elif len(str(b)) > 80:
        print("overflow")
    else :
        print(a + b)
a, b, x= raw_input().split()
m = a//b
if a%x == 0 or b%x == 0:
    print m+1
else:
    print m

### FIXED CODE ###

a, b, x= map(int, raw_input().split())
if a%x == 0:
    print b//x - a//x +1
else:
    print  b//x - a//x
n, m = map(int, input().split())
s = list(input())

g = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  # 1-indexed -> 0-indexed
    g[a].add(b)  # edge
    g[b].add(a)

q = [True for _ in range(n)]
left = n
i = 0
cnt_ok = 0
while left > 0:
    fa, fb = False, False
    for j in g[i]:
        if s[j] == 'A':
            fa = True
        elif s[j] == 'B':
            fb = True
        if fa and fb:
            break
    if fa and fb:
        cnt_ok += 1
        if cnt_ok == left:
            break
    else:
        s[j] = 'X'  # 除外された頂点
        q[i] = False
        left -= 1
        cnt_ok = 0
    i += 1
    if i == n:
        i = 0

print('Yes' if left > 0 else 'No')

### FIXED CODE ###

'''
https://beta.atcoder.jp/contests/agc027/submissions/3201641
'''
n, m = map(int, input().split())
s = list(input())

deg = [{'A':0, 'B':0} for _ in range(n)]  # deg[0 - (n - 1)][0 - 1] = 0
g = [list() for _ in range(n)]  # g[0 - (n - 1)] = []

for i in range(m):  # クエリを配列に代入
    x, y = map(int, input().split())
    x, y = x - 1, y - 1  # 1-indexed -> 0-indexed
    deg[x][s[y]] += 1  # 頂点 x に隣接する頂点の個数を管理 : A か B かに応じて, その文字のカウントを 1 増やす
    deg[y][s[x]] += 1  # 頂点 y に隣接する頂点の個数を管理 : A か B かに応じて, その文字のカウントを 1 増やす
    g[x].append(y)  # 頂点 x に隣接する頂点のリストに y を追加
    g[y].append(x)  # 頂点 y に隣接する頂点のリストに x を追加

was = [False for _ in range(n)]  # was[j] = True なら 頂点 j は que に追加済み
que = []  # A か B が隣接しないため, 連結リストから除外する頂点

for i in range(n):  # 全頂点をループ
    if deg[i]['A'] == 0 or deg[i]['B'] == 0:  # A か B が隣接しないなら
        que.append(i)  # 除外頂点リスト que に追加
        was[i] = True  #  was[j] = True は, 除外頂点リスト que に追加済を意味する

for q in que:  # A か B が隣接していない, 除外頂点リストの各頂点をループ（ que はループ中に追加されうる）
    for j in g[q]:  # 除外頂点に隣接する頂点をループ
        deg[j][s[q]] -= 1  # "除外頂点に隣接する頂点" に隣接する頂点の個数を管理 : 除外頂点の文字のカウントを減らす
        if deg[j]['A'] == 0 or deg[j]['B'] == 0:  # "除外頂点に隣接する頂点" に A か B が隣接しないなら
            if not was[j]:  # 頂点 j が que に追加済みの頂点でないなら, que に追加する / 追加済みなら, 隣接する頂点の個数管理は, 終了済み
                was[j] = True
                que.append(j)  # 除外頂点リスト que に追加, ループ回数増える

# 除外頂点を取り除いた後に, 頂点が残っていれば, AABB... を作成できる
# 頂点が残っていなければ, つまり, que に全ての頂点が入っていれば, AABB...を作成できない
print('No' if len(que) == n else 'Yes')
import math




def search3(S):
    harf = int(len(A)/3)
    for i, a in enumerate(A[harf:]):
        if a < S:
            A[i] = S
            return 
    return

def search2(S):
    harf = int(len(A)/2)
    for i, a in enumerate(A[harf:]):
        if a < S:
            A[i] = S
            return 
    return

def search(S):
    for i, a in enumerate(A):
        if a < S:
            A[i] = S
            return 
    return



def main():
    N = int(input())
    A[0] = int(input())
    m = A[0]
    harf = 0
    for _ in range(N-1):
        S = int(input())
        if S <= m:
            A.append(S)
        elif S <= th:
            search3(S)
        elif S <= harf:
            search2(S)
        else:
            search(S)
        m = A[-1]
        harf = A[int(len(A)/2)]
        th = A[int(len(A)/3)]
    print(len(A))

    

if __name__ == "__main__":
    A = [0]
    main()


### FIXED CODE ###

from bisect import bisect


def main():
    N = int(input())
    A = [-int(input()) for _ in range(N)]
    L = [A[0]]
    for a in A[1:]:
        if a >= L[-1]:
            L.append(a)
        else:
            L[bisect(L, a)] = a
    print(len(L))


if __name__ == "__main__":
    main()