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

N = int(input())
As = list(map(int, input().split()))
 
for i in range(1, N+1):
    print(As.count(i))
    As = [a for a in As if a != i]

### FIXED CODE ###

# coding: utf-8
# Your code here!

N = int(input())
As = list(map(int, input().split()))
ans = [0 for _ in range(N)]
 
for a in As:
    ans[a-1] += 1

print(*ans, sep="\n")
### BUGGY CODE ###

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

if N==1:
  if K%2:
    print(A[0])
  else:
    print('')
  exit()
  

#print(*range(10000))

def func(L):
  s = []
  for l in L:
    if l in s:
      del s[s.index(l):]
      #s_set.remove(l)
    else:
      s.append(l)
      #s_set.add(l)
  return s




index_dict={}
for i,a in enumerate(A):
  index_dict.setdefault(a,[]).append(i)

next_i = [0]*N
cycle_i = [0]*N
for k,v in index_dict.items():
  for i in range(len(v)):
    next_i[v[i]] = (v[(i+1)%len(v)]+1)%N
    cycle_i[v[i]] = (i+1)//len(v)

from_in_cycle=[]

i = 0
while True:
  j = next_i[i]
  if cycle_i[i]:
    from_in_cycle.append(i)
  i = j
  # 循環の評価
  if i==0:
    break
    
#print(from_in_cycle)

if from_in_cycle:
  k = K%(len(from_in_cycle)+1)
  print(*func(A[from_in_cycle[k-1]:]))
else:
  print('')

### FIXED CODE ###

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

if N==1:
  if K%2:
    print(A[0])
  else:
    print('')
  exit()
  

#print(*range(10000))

def func(L):
  s = []
  for l in L:
    if l in s:
      del s[s.index(l):]
      #s_set.remove(l)
    else:
      s.append(l)
      #s_set.add(l)
  return s




index_dict={}
for i,a in enumerate(A):
  index_dict.setdefault(a,[]).append(i)

next_i = [0]*N
cycle_i = [0]*N
for k,v in index_dict.items():
  for i in range(len(v)):
    next_i[v[i]] = (v[(i+1)%len(v)]+1)%N
    cycle_i[v[i]] = (i+1)//len(v)
#print(next_i)
#print(cycle_i)

from_in_cycle=[]

i = 0
while True:
  j = next_i[i]
  if cycle_i[i]:
    from_in_cycle.append(i)
  i = j
  # 循環の評価
  if i==0:
    break
    
#print(from_in_cycle)

if from_in_cycle:
  k = K%(len(from_in_cycle)+1)
  #print(*func(A[from_in_cycle[k-1]:]))

  ans = []
  i = from_in_cycle[k-1]
  while i < N:
    if cycle_i[i]:
      ans.append(A[i])
      i += 1
    else:
      if next_i[i]==0:
        break
      i = next_i[i]
  print(*ans)


else:
  print('')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Fri Jan  4 20:10:14 2019

@author: Yamazaki Kenichi
"""
import bisect

N, M= map(int,input().split())
C = [list(map(int,input().split())) for i in range(M)]

a = [[] for i in range(N)]
for j in range(M):
    a[C[j][0]-1].append(C[j][1])

for i in range(N):
    a[i].sort()

ans = []
for j in range(M):
    l = '0'*(6-len(str(C[j][0])))+str(C[j][0])
    r1 = a[C[j][0]-1].index(C[j][1])+1
    r = '0'*(6-len(str(r1)))+str(str(r1))
    ans = l + r 
    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Fri Jan  4 20:10:14 2019

@author: Yamazaki Kenichi
"""
import bisect

N, M= map(int,input().split())
C = [list(map(int,input().split())) for i in range(M)]

a = [[] for i in range(N)]
for j in range(M):
    a[C[j][0]-1].append(C[j][1])

for i in range(N):
    a[i].sort()

ans = []
for j in range(M):
    l = '0'*(6-len(str(C[j][0])))+str(C[j][0])
    r1 = bisect.bisect_left(a[C[j][0]-1],(C[j][1]))+1
    r = '0'*(6-len(str(r1)))+str(str(r1))
    ans = l + r 
    print(ans)
### BUGGY CODE ###

def main():
    import sys
    from collections import Counter

    input = sys.stdin.readline

    s = str(input().rstrip())
    num = ""
    li = []
    f = 0
    mi = 0
    li_append = li.append

    for i in range(1, len(s) + 1):
        num = s[-i] + num
        li_append(int(num) % 2019)
        if num[0] == "0":
            f += 1
        else:
            if f > 0:
                mi += ((f + 1) * f) // 2
                f = 0
            else:
                continue

    co = Counter(li)
    val = [i for i in co.values() if i > 1]
    ans_1 = 0

    for i in val:
        ans_1 += (i * (i - 1)) // 2
    ans2 = 0
    if 0 in co:
        ans2 = co[0]
    print(ans_1 + ans2 - mi)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    dic = defaultdict(int)

    input = sys.stdin.readline

    s = str(input().rstrip())
    m = 0
    before_m = 0.1

    for i in range(1, len(s) + 1):
        before_m = int(before_m*10)%2019
        m_ad = (int(s[-i]) * before_m) % 2019
        m = (m_ad + m) % 2019
        dic[m] += 1

    ans1 = 0

    for x in dic.values():
        if x > 1:
            ans1 += x * (x - 1) // 2
    ans2 = dic[0]

    print(ans1 + ans2)

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


from math import gcd
import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)

K = int(input())

ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += gcd(gcd(i+1,j+1), k+1)
print(ans)


### FIXED CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

K = int(input())
mod = 10**9 + 7

N = 3

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

ans = 0

M = np.zeros(K+1, dtype=int)

for i in range(K, 0, -1):
#    print(i)
    M[i] += pow(K//i, N)
    
    for j in range(2,K//i+1):
        j *= i
        M[i] -= M[j]
    
    ans += M[i] * i
    
        
print(ans)
### BUGGY CODE ###

n = int(input())
a = tuple(map(int, input().split()))
pos = 0
j = 1

while True:
    for i, data in enumerate(a[pos:]):
        if data == j:
            pos += i + 1
            j += 1
            break
    else:
        print((-1, n - j + 1)[j != 1])
        break


### FIXED CODE ###

n = int(input())
j = 1

for i in map(int, input().split()):
    if i == j:
        j += 1

print((-1, n - j + 1)[j != 1])
### BUGGY CODE ###

N=int(input())
minn=N-1
for i in range(N-1):
    if N%(i+1)==0 and minn>N//(i+1)-1+i:
        minn=N//(i+1)-1+i
if minn<=(N-1):
    print(minn)
else:
    print(N-1)

### FIXED CODE ###

N=int(input())
minn=N-1
for i in range(2,round((N)**0.5+1)):
    if N%i==0 and minn>N//(i)-2+i:
        minn=N//(i)-2+i
print(minn)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))

bit = [0] * 60
mod = 10 ** 9 + 7
ans = 0
for i in range(60):
    c = 0
    for x in a:
        if x >> i & 1:
            c += 1
    ans = (ans + c * (n - c) * (2 ** i)) % mod

print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))

bit = [0] * 60
mod = 10 ** 9 + 7
ans = 0
for i in range(60):
    n1 = np.count_nonzero((a >> i) & 1)
    n0 = n - n1
    ans += (2 ** i) * n1 * n0 % mod
print(ans % mod)
### BUGGY CODE ###

A, B, K = [int(i) for i in input().split()]

for i in range(0,K):
  if A >= 1:
    A = A - 1
  elif B >= 1:
    B = B - 1

print(A, B)

### FIXED CODE ###

A, B, K = [int(i) for i in input().split()]

jdg = K - A
A = A - min(A, K)
B = B - max(0, jdg)
B = max(0, B)
print(A, B)
### BUGGY CODE ###

from collections import deque

s = deque(list(input()))
q = int(input())
rev = False
for _ in range(q):
    qr = list(map(str, input().split()))
    if qr[0] == '1':
        s.reverse()
    else:
        if qr[1] == '1':
            s.appendleft(qr[2])
        else:
            s.append(qr[2])
print(''.join(s))

### FIXED CODE ###

s = input()
q = int(input())
a, b = "", ""
rev = False
for _ in range(q):
    qr = list(map(str, input().split()))
    if qr[0] == '1':
        rev = 1 - rev
    else:
        if qr[1] == '1':
            if rev: b += qr[2]
            else  : a += qr[2]
        else:
            if rev: a += qr[2]
            else  : b += qr[2]
if rev:
    print(b[::-1] + s[::-1] + a)
else:
    print(a[::-1] + s + b)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    x = input()

    for _ in range(10 ** 5):
        x = x.replace("ST", "")
        x = list(x)
        x = "".join(x)

    print(len(x))


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    x = input()

    cnt_S = 0
    cnt_T = 0
    res = 0
    i = 0
    while i < len(x):
        if x[i] == "S":
            cnt_S += 1
            i += 1

        elif x[i] == "T" and cnt_S != 0:
            while i < len(x) and x[i] == "T":
                cnt_T += 1
                i += 1
            res += min(cnt_S, cnt_T) * 2
            cnt_S -= min(cnt_S, cnt_T)
            cnt_T = 0
        else:
            i += 1

    print(len(x) - res)


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

import sys
from collections import deque
input = sys.stdin.readline
h, w = map(int, input().split())
g = []
for i in range(h):
    g.append(input())

move = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans = 0

for s_x, s_y in  [(i, j) for i in range(h) for j in range(w)]:
    if g[s_x][s_y] == "#":
        continue
    dp = [[0 for i in range(w)] for i in range(h)]
    pre = (-1, -1)
    cur = (s_x, s_y)
    cnt = 0
    queue = deque([(cur, pre, cnt)])
    queue_pop = queue.pop
    queue_append = queue.append
    while queue:
        cur, pre, cnt = queue_pop()
        c_x, c_y = cur
        if g[c_x][c_y] == '#':
          continue
        dp_cnt = dp[c_x][c_y]
        if not dp_cnt or dp_cnt > cnt:
            dp[c_x][c_y] = cnt

            for x, y in move:
                next = (cur[0] + x, cur[1] + y)
                if next == (s_x, s_y):
                    continue
                if next != pre and next[0] >= 0 and next[0] < h and next[1] >= 0 and next[1] < w:
                    queue_append([next, cur, cnt + 1])
    ans= max(max([dp[i][j] for i in range(h) for j in range(w)]), ans)


print(ans)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
h, w = map(int, input().split())
g = []
for i in range(h):
    g.append(input())

move = ((0, 1), (1, 0), (-1, 0), (0, -1))
ans = 0

for start in  [[i, j] for i in range(h) for j in range(w)]:
    if g[start[0]][start[1]] == "#":
        continue
    dp = [[0 for i in range(w)] for i in range(h)]
    pre = [-1, -1]
    cur = start
    cnt = 0
    queue = deque([[cur, pre, cnt]])
    while queue:
        cur, pre, cnt = queue.popleft()
        c_x, c_y = cur
        if g[c_x][c_y] == '#':
          continue
        if not dp[c_x][c_y] or (dp[c_x][c_y] and dp[c_x][c_y] > cnt):
            dp[c_x][c_y] = cnt

            for x, y in move:
                next = [cur[0] + x, cur[1] + y]
                if next == start:
                    continue
                if next != pre and next[0] >= 0 and next[0] < h and next[1] >= 0 and next[1] < w:
                    queue.append([next, cur, cnt + 1])
    ans= max(max([dp[i][j] for i in range(h) for j in range(w)]), ans)


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

import sys

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

def inZero(nums):
  return 0 in nums

def isOverDigits(nums):
  digits = 0

  for i in range(len(nums)):
    digits += len(str(nums[i])) - 1

  if digits > 18:
    return True
  else:
    return False

def calcAns(nums):
  ans = 1
  for i in range(len(nums)):
    ans = ans * nums[i]
  return ans

if inZero(a_list):
  print(0)
  sys.exit()

ans = calcAns(a_list) 

if ans > 10**18 :
  print(-1)
else :
  print(ans)





### FIXED CODE ###

import sys

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

def inZero(nums):
  return 0 in nums

def isOverDigits(nums):
  digits = 0

  for i in range(len(nums)):
    digits += len(str(nums[i])) - 1

  if digits > 18:
    return True
  else:
    return False

def calcAns(nums):
  ans = 1
  for i in range(len(nums)):
    ans = ans * nums[i]
    if ans > 10**18 :
      return False
  return ans

if inZero(a_list):
  print(0)
  sys.exit()

ans = calcAns(a_list) 

if ans :
  print(ans)
else :
  print(-1)
### BUGGY CODE ###

X, Y = map(int, input().split())
mod = 10**9 + 7

if (X + Y) % 3 != 0 or X > 2*Y or Y > 2*X:
    print(0)
else:
    n2x = (2*X - Y) // 3
    n1x = (2*Y - X) // 3
    n = n2x + n1x

    # nCn2xを求める
    def combs(n,n2x):
        invs = [1] * (n+1)
        nfac = 1
        for i in range(1, n+1):
            nfac = nfac * i % mod
            invs[i] = pow(nfac, mod-2, mod)
        return nfac * invs[n2x] * invs[n-n2x] % mod

    print(combs(n, n2x))


### FIXED CODE ###

X, Y = map(int, input().split())
mod = 10**9 + 7

if (X + Y) % 3 != 0 or X > 2*Y or Y > 2*X:
    print(0)
else:
    n2x = (2*X - Y) // 3
    n1x = (2*Y - X) // 3
    n = n2x + n1x

    # nCn2xを求める
    def combs(n,n2x):
        invs = [1] * (n+1)
        nfac = 1
        for i in range(1, n+1):
            nfac = nfac * i % mod
            invs[i] = pow(nfac, mod-2, mod)
        return nfac * invs[n2x] * invs[n-n2x] % mod

    print(combs(n, n2x))
### BUGGY CODE ###


import sys
input = sys.stdin.readline

N,W = map(int,input().split())

nap = []
sum_values = 0
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])
    sum_values += v1

INF = 10**15
dp = list([INF for _ in range(sum_values+1)] for _ in range(N+1))
dp[0][0] = 0

for i in range(N):
    w1, v1 = nap[i]
    for j in range(sum_values+1):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0

for j in range(sum_values+1):
    if dp[N][j] <= W:
        ans = j

print(ans)



### FIXED CODE ###


import sys
input = sys.stdin.readline

N,W = map(int,input().split())

nap = []
sum_values = 0
for i in range(N):
    w1,v1  = map(int,input().split())
    nap.append([w1,v1])
    sum_values += v1

INF = 10**15
dp = list([INF for _ in range(sum_values+1)] for _ in range(N+1))
dp[0][0] = 0

for i in range(N):
    w1, v1 = nap[i]
    for j in range(sum_values+1):
        if j - v1 >= 0:
            dp[i+1][j] = min (dp[i][j] , dp[i][j-v1] + w1 )
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j])
ans = 0

for j in range(sum_values+1):
    if dp[N][j] <= W:
        ans = j

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

s=input()
n=len(s)
mod=10**9+7
dp=[[0 for _ in range(13)] for _ in range(n)]
for i,x in enumerate(s):
    if i==0:
        if x=='?':
            for j in range(10):
                dp[0][j]=1
        else:
            num=ord(x)-ord('0')
            dp[0][num]=1
    else:
        if x=='?':
            for j in range(10):
                for jj in range(13):
                    if dp[i-1][jj]>0:
                        dp[i][(10*jj+j)%13]=(dp[i][(10*jj+j)%13]+dp[i-1][jj])%mod
        else:
            num=ord(x)-ord('0')
            for j in range(13):
                if dp[i-1][j]>0:
                    dp[i][(10*j+num)%13]=(dp[i][(10*j+num)%13]+dp[i-1][j])%mod
print(dp[-1][5])


### FIXED CODE ###

mod=10**9+7
s=input()
dp1=[1]+[0]*12
for i in range(len(s)):
    dp2=[0]*13
    if s[i]!='?':
        p=int(s[i])
        for j in range(13):
            dp2[(j*10+p)%13]+=dp1[j]
    else:
        for p in range(10):
            for j in range(13):
                dp2[(j*10+p)%13]+=dp1[j]
    dp1=[dp2[j]%mod for j in range(13)]
print(dp1[5])
### BUGGY CODE ###

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

def check(t):
    res = 0
    for ai in a:
        if ai:
            aj = t // ai
            if ai > 0:
                res += bisect.bisect_right(a, aj)
            else:
                if t % ai:
                    res += n - bisect.bisect_right(a, aj)
                else:
                    res += n - bisect.bisect_left(a, aj)
        else:
            if t >= 0:
                res += n
        if ai * ai <= t:
            res -= 1
    return res // 2

l = - 10 ** 18
r = 10 ** 18

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)

### FIXED CODE ###

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

a.sort()

def check(t):
    j = n - 1 if t > 0 else 0
    res = 0
    f = 1

    cond = lambda x, t, f:x <= t if f * t > 0 or (t == 0 and f == -1) else x > t
    shift = lambda x, t:x-1 if t > 0 else x+1
    count = lambda x, n, f:n-x if f == 1 else x

    for ai in a:
        if f == 1 and ai > 0:
            f = -1
            j = n - 1 if t > 0 else 0
        if ai:
            while j >= 0 and j < n and cond(ai * a[j], t, f):
                j = shift(j, t)
            if t > 0:
                res += count(j+1, n, f)
            else:
                res += count(j, n, f)
        else:
            if t >= 0:
                res += n
        if ai * ai <= t:
            res -= 1
    return res // 2
            

m = max(max(a)**2, min(a)**2)
l = -m
r = m

while r - l > 1:
    mid = (l + r) // 2
    if check(mid) < k:
        l = mid
    else:
        r = mid

if check(l) == k:
    print(l)
else:
    print(r)
### BUGGY CODE ###

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

a.sort()
count = 0

while x > min(a):
    pass
for i in a:
    if x >= i:
        x -= i
        count += 1
    else:
        pass
        
print(count)

### FIXED CODE ###

N, x = map(int, input().split())
a = sorted(map(int, input().split()))
cnt = 0
for i in a:
    if x < i:
        break
    cnt += 1
    x -= i
else:
    if x > 0:
        cnt -= 1
print(cnt)
### BUGGY CODE ###

def main():
    S = input()
    li = []
    li_append = li.append
    is_A = False
    now_state = 0
    for ind,s in enumerate(S):
        if(is_A):
            if(now_state==1):
                now_state = 0
                continue
            else:
                if(s=='A'):
                    li[-1] += 'A'
                elif(S[ind:ind+2]=='BC'):
                    li[-1] += 'B'
                    now_state = 1
                else:
                    is_A = False
        elif(s=='A'):
            is_A = True
            now_state = 0
            li_append('A')
    cnt = 0
    for i in li:
        cntb = i.count('B')
        for ind,s in enumerate(i):
            if(s=='A'):
                cnt += cntb
            elif(s=='B'):
                cntb -= 1
    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = input()
    li = []
    li_append = li.append
    is_A = False
    now_state = 0
    for ind,s in enumerate(S):
        if(is_A):
            if(now_state==1):
                now_state = 0
                continue
            else:
                if(s=='A'):
                    li[-1].append(0)
                elif(S[ind:ind+2]=='BC'):
                    li[-1][-1] += 1
                    now_state = 1
                else:
                    is_A = False
        elif(s=='A'):
            is_A = True
            now_state = 0
            li_append([0])
    cnt = 0
    for i in li:
        cnt_b = sum(i)
        for j in i:
            cnt += cnt_b
            cnt_b -= j
            
    print(cnt)

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

import math
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)


S = readChar()

re = [0]*len(S)

for i in range(1,len(S)+1):
	re[i*-1] = int(S[i*-1])*pow(10,i-1,2019)%2019

res = [0]*len(S)
for j in range(1,len(S)+1):
	res[j*-1] = sum(re[j*-1:])%2019

d = defaultdict(int)
for i in res:
	d[i]+=1

ans = d[0]
for key in d:
	if d[key]>1:
		ans+=comb(d[key],2)

print(ans)

### FIXED CODE ###

import math

def readInt():
	return int(input())

def readInts():
	return list(map(int, input().split()))

def readChars():
	return input().split()

s = reversed(input())

ai = 0
si = 0

p = 2019
countarr = [0]*2019

for i, j in enumerate(s):
	ai = (int(j)*pow(10,i,p))%p
	si = (si+ai)%p
	countarr[si]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)
### BUGGY CODE ###

def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    n = int(input())
    a_list = [int(input()) for _ in range(n)]

    color_list = []

    for a in a_list:
        # 既存の色でぬれるかチェック
        can_draw = False
        # 増分が一番小さいものを選ぶ
        best_diff = 10 ** 9 + 1
        best_index = -1
        for index, color in enumerate(color_list):
            if color < a:
                can_draw = True
                diff = a - color
                if diff < best_diff:
                    best_diff = diff
                    best_index = index
        if can_draw:
            color_list[best_index] = a
        else:
            color_list.append(a)
        # print(color_list)
    # print()
    # print(color_list)
    print(len(color_list))

# a1から順番に塗っていく
# 色ごとに、今まで塗った最大値を記録する
# 既存の色でぬれる場合は、なるべく最大値の増分が少なくなるように色を選ぶ
# 既存の色でぬれない場合は新しい色を作って最大値を記録する


### FIXED CODE ###

from bisect import bisect_left


def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    n = int(input())
    a_list = [int(input()) for _ in range(n)]

    color_list = [-1] * n
    color_num = 0

    for a in a_list:
        # ２分探索
        index = bisect_left(color_list, a)
        # print(index)
        color_list[index - 1] = a
        if n - index == color_num:
            color_num = color_num + 1
        # print(color_list)
    # print()
    # print(color_list)
    print(color_num)

# a1から順番に塗っていく
# 色ごとに、今まで塗った最大値を記録する
# 既存の色でぬれる場合は、なるべく最大値の増分が少なくなるように色を選ぶ
# 既存の色でぬれない場合は新しい色を作って最大値を記録する
### BUGGY CODE ###

from collections import Counter
from scipy.misc import comb

N = int(input())
A = list(map(int, input().split()))
ans = 0
cumulative_sum = [0] + [sum(A[:i+1]) for i in range(N)]
counts = Counter(cumulative_sum).most_common()
ans = 0
for c in counts:
    if c[1] < 2:
        break
    ans += comb(c[1], 2, exact=True)
    
print(ans)


### FIXED CODE ###

from collections import Counter
import numpy as np

N = int(input())
A = [0]+list(map(int, input().split()))

cumulative_sum = np.cumsum(A)
counts = Counter(cumulative_sum)
ans = 0
for v in counts.values():
    ans += v * (v-1) // 2
    
print(ans)
### BUGGY CODE ###

n, m, r = map(int,input().split())
R = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(m)]

M = [[float("inf")] * (n+1) for i in range(n+1)]

for i in range(1, n+1):
    M[i][i] = 0
for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            if k <= i:
                M[i][j] = min(M[i][j], M[k][i] + M[k][j])
            elif k <= j:
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
            else:
                M[i][j] = min(M[i][j], M[i][j] + M[j][k])

# 上のコードだとTLE

# from scipy.sparse.csgraph import floyd_warshall
# M = floyd_warshall(M)

import itertools
R1 = list(itertools.permutations(R))

ans = float("inf")
for i in range(len(R1)):
    ans1 = 0
    for j in range(r-1):
        ans1 += M[R1[i][j]][R1[i][j+1]]
    ans = min(ans, ans1)

print(int(ans))


### FIXED CODE ###

n, m, r = map(int,input().split())
R = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(m)]

M = [[float("inf")] * (n+1) for i in range(n+1)]

for i in range(1, n+1):
    M[i][i] = 0
for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

# for k in range(1, n+1):
#     for i in range(1, n+1):
#         for j in range(1, n+1):
#             M[i][j] = min(M[i][j], M[i][k] + M[k][j])

from scipy.sparse.csgraph import floyd_warshall
M = floyd_warshall(M)

import itertools
R1 = list(itertools.permutations(R))

ans = float("inf")
for i in range(len(R1)):
    ans1 = 0
    for j in range(r-1):
        ans1 += M[R1[i][j]][R1[i][j+1]]
    ans = min(ans, ans1)

print(int(ans))