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

import numpy as np

N, M = (list(map(int, input().split())))
a = np.array([0]*M)
b = np.array([0]*M)
for i in range(M):
  a[i], b[i] = (input().split())
ans = 0
C = set()
D = set()
for i in range(M):
  count = 0
  boo = True
  while(boo):
    for j in range(M):
      if i != j:
        if(count == 0):
          C.add(a[j])
          C.add(b[j])
          count += 1
        if C <= {a[j]} or C <= {b[j]}:
          C.add(a[j])
          C.add(b[j])
    if(D in C):
      boo = False
      break
    else:
      D = C
  if(len(C) == N):
    ans += 1
print(ans)

### FIXED CODE ###

import numpy as np
 
N, M = (list(map(int, input().split())))
a = np.array([0]*M)
b = np.array([0]*M)
for i in range(M):
  a[i], b[i] = (input().split())
ans = M
for i in range(M):
  C = set()
  D = set()
  count = 0
  while(True):
    for j in range(M):
      if not i == j:
        if(count == 0):
          C.add(a[j]) 
          C.add(b[j])
          count += 1  
        if a[j] in C or b[j] in C:
          C.add(a[j])
          C.add(b[j])
    if(C == D):
      break
    else:
      D = C.union(D)
  if(len(C) == N):
    ans -= 1
print(ans)
### BUGGY CODE ###

def z_algo(s):
    N = len(s)
    A = [0]*N
    i = 1; j = 0
    l = len(s)
    A[0] = l
    while i < l:
        while i+j < l and s[j] == s[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
        # 自身は含まない
    A[0] = 0
        #
    return A

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = []

N = I()
S = str(input())
cur = int(0)
ans = int(0)
lenC = []

for i in range(N):
#    print(z_algo(S[i:]))
    lenC.append(max(z_algo(S[i:])))

#print(lenC)
ans = min(max(lenC),N//2)
print(ans)


### FIXED CODE ###

def z_algo(s):
    N = len(s)
    A = [0]*N
    i = 1; j = 0
    l = len(s)
    A[0] = l
    B = [0]*N
    while i < l:
        while i+j < l and s[j] == s[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k

    # 自身は含まない
    for i in range(N):
        B[i] = i
    #
    for i in range(N):
        A[i] = min(A[i],i)
#    print(B)
#    A[0] = 0
    return A

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = []

N = I()
S = str(input())
cur = int(0)
ans = int(0)
lenC = []

for i in range(N):
#    print(z_algo(S[i:]))
    lenC.append(max(z_algo(S[i:])))

#print(lenC)
ans = min(max(lenC),N//2)
print(ans)
### BUGGY CODE ###

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

p = 10 ** 9 + 7
N = 10 ** 5 *5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


def f(x):
    if x==1:
        return 2
    elif x==2:
        return 4
    elif x%2==0:
        return f(x//2)**2
    else:
        return f(x//2)**2*2


fact2 = []
fact2num = max(a,b)+2
now = 1
for i in range(fact2num):
    now *= (n-i)
    now %= p
    fact2.append(now)

def ncr(n,r):
    return (fact2[r-1]*factinv[r])%p

print(f(n)-1-ncr(n,a)-ncr(n,b))


### FIXED CODE ###

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

p = 10 ** 9 + 7
N = 10 ** 5 *5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


# def f(x):
#     if x==1:
#         return 2
#     elif x==2:
#         return 4
#     elif x%2==0:
#         return f(x//2)**2
#     else:
#         return f(x//2)**2*2

di131072 = 1
for i in range(131072):
    di131072 *= 2
    di131072 %= p

q = n//131072
r = n%131072
ans = 1
for i in range(q):
    ans *= di131072
    ans %= p
for i in range(r):
    ans *= 2
    ans %= p


fact2 = []
fact2num = max(a,b)+2
now = 1
for i in range(fact2num):
    now *= (n-i)
    now %= p
    fact2.append(now)

def ncr(n,r):
    return (fact2[r-1]*factinv[r])%p


print((ans-1-ncr(n,a)-ncr(n,b))%p)
### BUGGY CODE ###

mod = 10**9+7
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]

dp = [0] * (N + 1)
dp[:2] = 1, 1 if 1 not in a else 0

for i in range(2, N+1):
    if not i in a:
        dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[-1])


### FIXED CODE ###

mod = 10**9+7
N, M = map(int, input().split())
a = set(int(input()) for _ in range(M))

dp = [0] * (N + 1)
dp[:2] = 1, 1 if 1 not in a else 0

for i in range(2, N+1):
    # in listでは間に合わない
    if not i in a:
        dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[-1])
### BUGGY CODE ###

# 素数リスト生成
def sieve(x):
    if x < 2: return []
    primes = [i for i in range(x)]
    primes[1] = 0
    for p in primes:
        if p > x ** (1/2): break
        if p == 0: continue
        for np in range(2 * p, x, p): primes[np] = 0
    return [p for p in primes if p != 0]

PS = sieve(10**9)

# 素因数分解
def factorint(x):
  d = {}
  for k in PS:
    if(x % k== 0):
      m = 1
      while(x % (k**m) == 0):
        m += 1
      d[k] = m - 1
      x = x / (k ** (m - 1))
      if x == 1:
        break
  return d

n, m = map(int, input().split())
f = factorint(m)
idx = [i for i in f.values()]

def fact(n):
  ret = 1
  for i in range(1, n + 1):
    ret *= i
  return ret
def com(n, r):
  if n - r < r: r = n - r
  ret = 1
  for i in range(n-r+1, n+1):
    ret *= i
  for j in range(1, r+1):
    ret //= j
  return ret

ans = 1
for i in range(len(idx)):
  ans *= com(idx[i] + n - 1, n - 1) % (10 ** 9 + 7)

print(ans % (10 ** 9 + 7))

### FIXED CODE ###

# 素数リスト生成
def sieve(x):
    if x < 2: return []
    primes = [i for i in range(x)]
    primes[1] = 0
    for p in primes:
        if p > x ** (1/2): break
        if p == 0: continue
        for np in range(2 * p, x, p): primes[np] = 0
    return [p for p in primes if p != 0]

PS = sieve(10**6)

# 素因数分解
def factorint(x):
  d = {}
  for k in PS:
    if(x % k== 0):
      m = 1
      while(x % (k**m) == 0):
        m += 1
      d[k] = m - 1
      x = x / (k ** (m - 1))
      if x == 1:
        break
  return d

n, m = map(int, input().split())
f = factorint(m)
idx = [i for i in f.values()]
# 10^6より大きい素因数があったときの処理
re = 1
for k, v in f.items():
  re *= k**v
if m // re != 1:
  idx.append(1)


def fact(n):
  ret = 1
  for i in range(1, n + 1):
    ret *= i
  return ret
def com(n, r):
  if n - r < r: r = n - r
  ret = 1
  for i in range(n-r+1, n+1):
    ret *= i
  for j in range(1, r+1):
    ret //= j
  return ret

ans = 1
for i in range(len(idx)):
  ans *= com(idx[i] + n - 1, n - 1) % (10 ** 9 + 7)

  
print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

import sys

def solve():
    input = sys.stdin.readline
    T = int(input())
    Ans = [0] * T
    for t in range(T):
        N = int(input())
        A = [int(a) for a in input().split()]
        S = input().strip("\n")
        used = {0}
        for i in reversed(range(N)):
            if S[i] == "0":
                new = set()
                for k in used:
                    new |= {k ^ A[i]}
                used |= new
            else:
                if A[i] not in used: 
                    Ans[t] = 1
                    break
                
    
    print(*Ans, sep="\n")

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from copy import deepcopy

def canMake(k, Nums):#Numsにある数でkを作れるか
    L = len(Nums)
    index = 0
    bit = []
    for i in reversed(range(60)):
        flag = 0
        for j in range(index, L):
            if Nums[j] & (1 << i) == (1 << i):
                flag = 1
                Nums[index], Nums[j] = Nums[j], Nums[index]
                bit.append(i)
                break
        if flag == 1:
            for j in range(L):
                if Nums[j] & (1 << i) == (1 << i) and index != j: Nums[j] ^= Nums[index]
        if flag == 1: index += 1
    ans = 0
    for i in range(60):
        if k & (1 << i) == (1 << i):
            if i in bit: ans ^= Nums[bit.index(i)]
    if ans == k: return True
    else: return False


def solve():
    input = sys.stdin.readline
    T = int(input())
    Ans = [0] * T
    for t in range(T):
        N = int(input())
        A = [int(a) for a in input().split()]
        S = input().strip("\n")
        used = []
        for i in reversed(range(N)):
            if S[i] == "0":
                used.append(A[i])
            else:
                compare = deepcopy(used)
                if not canMake(A[i], compare):
                    Ans[t] = 1
                    break
    
    print(*Ans, sep="\n")

    return 0

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

# 2019/08/11

from fractions import gcd

n,m=map(int,input().split())
s=list(input())
t=list(input())
lcd=(n*m)//gcd(n,m)
x=['' for _ in range(lcd)]

for i in range(max(n,m)):
    if i<n:
        a=i*(lcd//n)
        if x[a]==s[i] or x[a]=='':
            x[a]=s[i]
        else:
            print(-1)
            exit()
    if i<m:
        b=i*(lcd//m)
        if x[b]==t[i] or x[b]=='':
            x[b]=t[i]
        else:
            print(-1)
            exit()
        
print(lcd)


### FIXED CODE ###

# 2019/08/11

from fractions import gcd

n,m=map(int,input().split())
s=input()
t=input()
lcd=(n*m)//gcd(n,m)
x={}
aa=(lcd//n)
bb=(lcd//m)
for i in range(n):
    a=i*aa
    x[a]=s[i]

for i in range(m):
    b=i*bb
    if b in x and x[b]!=t[i]:
        print(-1)
        exit()
    
print(lcd)
### BUGGY CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 2回目で0か2しかない場合と1がある場合
# 1がある時は2は0に変換して良い

def lucas(n, r):
    # nCr が奇数ならTrueを返す
    N = bin(n)[2:]; R = bin(r)[2:]
    ret = 1
    for x, y in zip(N[::-1], R[::-1]):
        if x == '0' and y == '1':
            ret = 0; break
    return ret

N = ir()
A = np.array(list(map(int, sr())))
A = np.abs(np.diff(A))
N -= 1
bl = False
if 1 not in set(A):
    bl = True
    A //= 2

# それぞれの値が答えに何回貢献しているか
result = 0
A = A.tolist()
for i, a in enumerate(A):
    result += a * lucas(N-1, i)
result %= 2

print(result * 2 if bl else result)


### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 2回目で0か2しかない場合と1がある場合
# 1がある時は2は0に変換して良い

def lucas(B, r):
    # nCr が奇数ならTrueを返す
    R = bin(r)[2:]
    for x, y in zip(B[::-1], R[::-1]):
        if x == '0' and y == '1':
            return 0
    return 1

N = ir()
A = np.array(list(map(int, sr())))
A = np.abs(np.diff(A))
N -= 1
bl = False
if 1 not in set(A):
    bl = True
    A //= 2

# それぞれの値が答えに何回貢献しているか
result = 0
A = A.tolist()
B = bin(N-1)[2:]
for i, a in enumerate(A):
    result += a * lucas(B, i)
result %= 2

print(result * 2 if bl else result)
### BUGGY CODE ###

from itertools import permutations


def warshall_floyd(d):
    m = min
    #d[i][j]: iからjへの最短距離
    n = len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = m(d[i][j], d[i][k] + d[k][j])
    return d


N, M, R = [int(x) for x in input().split()]
r = [int(x)-1 for x in input().split()]

INF = float("inf")
route_list = [[INF]*N for _ in range(N)]

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

wa_list = warshall_floyd(route_list)
ans = 30**9

for perm in permutations(r):
    # print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)


### FIXED CODE ###

from itertools import product, permutations


def warshall_floyd(d):
    # d        : nxn adjacent matrix
    for k, i, j in product(range(n), repeat=3):
        if d[i][j] > d[i][k] + d[k][j]:
            d[i][j] = d[i][k] + d[k][j]


INF = float("inf")
n, m, r = map(int, input().split())
r_list = list(map(lambda x: int(x) - 1, input().split()))
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    d[a][b] = d[b][a] = c
warshall_floyd(d)

ans = float("inf")
for np in permutations(r_list):
    cand = sum([d[np[i]][np[i + 1]] for i in range(r - 1)])
    ans = min(ans, cand)

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

import sys
# input = sys.stdin.buffer.readline
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

MAX = 1200000    # 80*80*80=512000

H, W = map(int, input().split())
A = [[int(x) for x in input().split()] for _ in range(H)]
B = [[int(x) for x in input().split()] for _ in range(H)]
C = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j] - B[i][j])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(C[0][0])
for i in range(H):
    for j in range(W):
        if i:
            for k in dp[i-1][j]:
                dp[i][j].add(abs(k+C[i][j]))
                dp[i][j].add(abs(k-C[i][j]))
        if j:
            for k in dp[i][j-1]:
                dp[i][j].add(abs(k+C[i][j]))
                dp[i][j].add(abs(k-C[i][j]))
print(min(dp[H-1][W-1]))


### FIXED CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
B = [list(map(int, input().split())) for i in range(H)]
center = 80 * (H+W)
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

dp = [[0] * W for i in range(H)]
dp[0][0] = (1 << (center + C[0][0])) | (1 >> (center - C[0][0]))

for i in range(H):
    for j in range(W):
        if i:
            dp[i][j] |= dp[i-1][j] << C[i][j]
            dp[i][j] |= dp[i-1][j] >> C[i][j]
        if j:
            dp[i][j] |= dp[i][j-1] << C[i][j]
            dp[i][j] |= dp[i][j-1] >> C[i][j]

ans = center * 2
for i in range(center*2):
    if (dp[H-1][W-1] >> i) & 1:
        ans = min(ans, abs(i-center))

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

from collections import defaultdict
from functools import lru_cache
import numpy as np


def trial_division(n):
    factor = defaultdict(int)
    tmp = int(np.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor[num] += 1
    factor[n] += 1
    return factor


@lru_cache(maxsize=None)
def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
numbers = defaultdict(int)
for a_i in a:
    for i, v in trial_division(a_i).items():
        numbers[i] = max(v, numbers[i])

l = 1
for i, v in numbers.items():
    l *= i ** v
    l %= mod


ans = 0
for i in a:
    r = powmod(i, mod-2, mod)
    ans += l * r
    ans %= mod
print(int(ans))




### FIXED CODE ###

from collections import defaultdict
from functools import lru_cache
import math


def trial_division(n):
    factor = defaultdict(int)
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor[num] += 1
    factor[n] += 1
    return factor


@lru_cache(maxsize=None)
def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
numbers = defaultdict(int)
for a_i in a:
    for i, v in trial_division(a_i).items():
        numbers[i] = max(v, numbers[i])

l = 1
for i, v in numbers.items():
    l *= powmod(i, v, mod)
    l %= mod


ans = 0
for i in a:
    r = powmod(i, mod-2, mod)
    ans += l * r
    ans %= mod
print(int(ans))
### BUGGY CODE ###

N = int(input())
nums = [int(input()) for i in range(N)]
ans = []
count = 0

for num in nums:
    try:
        idx = ans.index(num)
    except ValueError:
        idx = -1
        
    if idx == -1:
        ans.append(num)
        count += 1
    else:
        ans[idx] = 0
        count -= 1

print(count)


### FIXED CODE ###

N = int(input())
nums = [int(input()) for i in range(N)]
idxs = set(nums)
ans = {idxs.pop() : 0 for i in range(len(idxs))}
count = 0

for num in nums:
    ans[num] += 1

for i in ans.keys():
    ans[i] = (ans[i] % 2)

print(sum(ans.values()))
### BUGGY CODE ###

def calc(N, S):
    id = {'R': 0, 'G': 1, 'B': 2}
    rgb = [[0, 0, 0] for _ in range(N)]
    rgb[0][id[S[0]]] = 1
    for i in range(1, N):
        for j in [0, 1, 2]:
            rgb[i][j] = rgb[i - 1][j]
            if j == id[S[i]]:
                rgb[i][j] += 1
    result = 0
    for i in range(N - 1, -1, -1):
        X = S[i]
        YZ = (['G', 'B'] if X == 'R' else ['R', 'B'] if X == 'G' else ['R', 'G'])
        j = i - 1
        while j > -1:
            if S[j] in YZ:
                result += rgb[j][3 - id[X] - id[S[j]]]
                if 2 * j - i > -1 and not S[2 * j - i] in [X, S[j]]:
                    result -=1
            j -= 1
    return result


N = int(input())
S = input()
print(calc(N, S))

### FIXED CODE ###

def calc(N, S):
    id = {'R': 0, 'G': 1, 'B': 2}
    rgb = [[0, 0, 0] for _ in range(N)]
    rgb[0][id[S[0]]] = 1
    for i in range(1, N):
        for j in [0, 1, 2]:
            rgb[i][j] = rgb[i - 1][j]
            if j == id[S[i]]:
                rgb[i][j] += 1
    result = 0
    for i in range(N - 1, -1, -1):
        X = S[i]
        YZ = (['G', 'B'] if X == 'R' else ['R', 'B'] if X == 'G' else ['R', 'G'])
        j = i - 1
        while j > -1:
            if S[j] in YZ:
                result += rgb[j][3 - id[X] - id[S[j]]]
                if 2 * j - i > -1 and not S[2 * j - i] in [X, S[j]]:
                    result -=1
            j -= 1
    return result


N = int(input())
S = input()
print(calc(N, S))
### BUGGY CODE ###

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]

xy.sort(key=lambda x:x[1])
for i in range(N):
    xy[i][1] = i+1

xy.sort()
for i in range(N):
    xy[i][0] = i

# x<xi,y<yi
l1 = [0]*N
# x<xi,y>yi
l2 = [0]*N
# x>xi,y<yi
r1 = [0]*N
# x>xi,y>yi
r2 = [0]*N

bitl = BIT(N)
for i in range(N):
    l1[i] = bitl.sum(xy[i][1])
    l2[i] = i-l1[i]
    bitl.add(xy[i][1],1)

bitr = BIT(N)
for i in range(N):
    r1[N-i-1] = bitr.sum(xy[N-i-1][1])
    r2[N-i-1] = i-r1[N-i-1]
    bitr.add(xy[N-i-1][1],1)

ans = pow(2,N-1,mod)*N
for i in range(N):
    L1 = pow(2,l1[i],mod)
    L2 = pow(2,l2[i],mod)
    R1 = pow(2,r1[i],mod)
    R2 = pow(2,r2[i],mod)
    ans += L1*L2*R1*R2
    ans -= L1*R1
    ans -= L2*R2
    ans -= L1*L2
    ans -= R1*R2
    ans += L1+L2+R1+R2-1
    ans %= mod

print(ans)

### FIXED CODE ###

from operator import itemgetter

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=itemgetter(1))
for i in range(N):
    xy[i][1] = i+1
xy.sort(key=itemgetter(0))

pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow2[N-1]*N%mod

bit = BIT(N)
for i in range(N):
    l1 = bit.sum(xy[i][1])
    l2 = i-l1
    r1 = xy[i][1]-l1-1
    r2 = N-xy[i][1]-l2
    bit.add(xy[i][1],1)
    ans += (pow2[l2]-1)*(pow2[r1]-1)*pow2[r2]*pow2[l1]
    ans += (pow2[r2]-1)*(pow2[l1]-1)*(pow2[l2]+pow2[r1]-1)
    ans %= mod

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

import numpy as np
n, m = map(int, input().split())
bridge = []
for i in range(m):
    bridge += list(map(int, input().split()))
bridge = np.array(bridge).reshape(m, 2)
total = n*(n-1)//2
ans =[total]
u = [i for i in range(n+1)]
def unite(x, y, total, ans, u):
    X, Y = sorted([find(x), find(y)])
    if X != Y:
        total -= u.count(u[X]) * u.count(u[Y])
        ans += [total]
        u = [Y if i == X else i for i in u]
    else:
        ans += [total]
    return ans, total, u

def find(x):
    if x != u[x]:
        x =u[x]
        find(x)
    return x

def size(x):
    u.count(abs(u[x]))
for x , y in bridge[::-1]:
    ans, total, u = unite(x, y, total, ans, u)

ans = ans[:-1]
print(*ans[::-1], sep="\n")


### FIXED CODE ###

import sys
n , m, *e = map(int,sys.stdin.read().split())
total = n*(n-1)//2
ans =[total]
u = [-1]*(n+1)

def find(x):
    if u[x] < 0 :
        return x
    else:
        return find(u[x])

for x , y in zip(e[-2:1:-2],e[:1:-2]):
    x = find(x)
    y = find(y)
    x, y = sorted((x, y))
    if x != y:
        total -= u[x] * u[y]
        u[x] += u[y]
        u[y] = x
    ans += [total]

print(*ans[::-1], sep="\n")
### BUGGY CODE ###

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

def main():
  a,b = map(int, input().split())
  g = gcd(a,b)
  N = int(g*0.5)
  ans = 1
  for i in range(2, N+1):
    flag = 0
    while(g%i==0):
      g /= i
      flag = 1
    ans += flag
  if g != 1:
    ans += 1
  print(ans)

main()

### FIXED CODE ###

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

a,b = map(int, input().split())
g = gcd(a,b)
N = int(g**0.5)
ans = 1
for i in range(2, N+1):
  if g%i==0:
    ans += 1
  while(g%i==0):
    g /= i
if g != 1:
  ans += 1
print(ans)
### BUGGY CODE ###

s = input()
t = input()

def replacement(word, a, b):
    return word.replace(a, "0").replace(b, a).replace("0", b)

yet_list = []
for i in range(len(s)):
    if s[i] != t[i]:
        if not s[i] in yet_list:
            s = replacement(s, s[i], t[i])
            yet_list.append(s[i])
            yet_list.append(t[i])
if s == t:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
s = input()
t = input()
yetlist = {}
yetlist2 = {}
for i in range(len(s)):
    if s[i] in yetlist:
        if t[i] != yetlist[s[i]]:
            print("No")
            sys.exit()
    else:
        yetlist[s[i]] = t[i]
    if t[i] in yetlist2:
        if s[i] != yetlist2[t[i]]:
            print("No")
            sys.exit()
    else:
        yetlist2[t[i]] = s[i]   
            
print("Yes")
### BUGGY CODE ###

from bisect import bisect

icase=0
if icase==0:
    n=int(input())
    a=[0]*n
    for i in range(n):
        a[i]=int(input())

def loopa(a):

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -1
    dq = [0]*(n+1)    
    
    for i in range(n):
        idx = bisect(dp, a[i]-1)
        if dp[idx]==10**10:
#            dp[idx] = min(a[i], dp[idx])
            if dp[idx]>a[i]:
                dp[idx]=a[i]
                dq[idx]=i
            dp2=dp[1:idx+1]
            dq2=dq[1:idx+1]
        else:
#            dp[idx] = min(a[i], dp[idx])
            if dp[idx]>a[i]:
                dp[idx]=a[i]
                dq[idx]=i


#    dq2.sort() 
#    for i in range(len(dq2)-1,-1,-1):
#        del a[dq2[i]]
#    print(dq2)
    a=[a[i] for i in range(n) if not (i in dq2)]
    return a

icnt=0
while len(a)>0:
#    if icnt>10:break
    a=loopa(a)        
    icnt+=1

print(icnt)    


### FIXED CODE ###

from bisect import bisect

icase=1
if icase==1:
    n=int(input())
    a=[0]*n
    for i in range(n):
        a[i]=-int(input())
elif icase==2:
    n=5
    a=[-2,-1,-4,-5,-3]
elif icase==3:
    n=4
    a=[0,0,0,0]

def loopa():

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -10**10
    
    for i in range(n):
#        idx = bisect(dp, a[i]-1)
        idx = bisect(dp, a[i])
        dp[idx] = min(a[i], dp[idx])

#        print("i:",i,"a:",a,"dp2:",dp2)            
    return dp

dp=loopa()        

print(bisect(dp, 10**10-1)-1)