Harryxun/stf_run huggingface dataset:
import collections
N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)

ans = 0
for i in C.values():
    ans += int(0.5* i * (i-1))
for j in A:
    print(ans-C[j]+1)


### FIXED CODE ###

from collections import deque
S = str(input())
Q = int(input())
query = [ input().split() for _ in range(Q) ]

tag = False
que = deque([S])

for i in range(Q):
    if query[i][0] == str(1):
        if tag == False:
            tag = True
        else:
            tag = False
    elif query[i][0] == str(2):
        if query[i][1] == str(1):
            if tag == False:
                que.appendleft(query[i][2])
            else:
                que.append(query[i][2])
        else:
            if tag == False:
                que.append(query[i][2])
            else:
                que.appendleft(query[i][2])
ans = "".join(que)
if tag == True:
    ans = ans[::-1]
print(ans)
a = input(b)
b = {"A" : "T", "G" : "C", "T" : "A", "C" : "G"}

print(c[b])

### FIXED CODE ###

a = input()
b = {"A" : "T", "G" : "C", "T" : "A", "C" : "G"}

print(b[a])
a, b = [], []
while True:
    try:
        x, y = map(int, line.strip().split(","))
        a, b = a+[x*y], b+[y]
    except:
        break
print(sum(a))
print(round(sum(b)/len(b)))

### FIXED CODE ###

ans = [0, 0]
cnt = 0
while True:
    try:
        x, y = map(int, input().split(','))
        cnt += 1
    except:
        break
    ans[0] += x*y
    ans[1] += y
ans[1] = ans[1]/cnt
if int(str(ans[1]).split(".")[0]) > 4:
    ans[1] += 1
ans[1] = int(ans[1])
print(*ans, sep="\n")
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n

for i, hi in enumerate(h):
    s = max(i-k,0)
    dp[i] = min(dpj + abs(hi - hj) for dpj, hj in zip(dp, h):
    
print(dp[-1])


### FIXED CODE ###

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

dp = [0] * n

for i in range(1, n):
    hi = h[i]
    s = max(i-k,0)
    dp[i] = min(dpj + abs(hi - hj) for dpj, hj in zip(dp[s:i], h[s:i]))
    
print(dp[-1])
n, m = map(int, input().split())

fail = False
result = {}
for i in range(0, m):
    s, c = map(int, input().split())
    key = n-s
    if key in result and result[key] != c:
        fail = True
        break
    result[key] = c

if not(n-1 in result) or result[n-1] == 0:
   fail = True

if fail:
    print(-1)
else:
    res = 0
    for i in range(0, n):
        if i in result:
            res += 10 ** i * result[i]
    print(res)


### FIXED CODE ###

n = int(input())
print(int((n+1)/2))
import numpy as np
 
mod = 10**9 + 7
N = input()
A = np.array(list(map(int, input().split())), dtype='uint64') % mod
A = np.atleast_2d(A)

print((np.sum((A ^ A.T) % mod) % mod) // 2)

### FIXED CODE ###

import numpy as np
 
mod = 10**9 + 7
max_digit = 60
N = int(input())
A = np.array(list(map(int, input().split())))

result = 0
base = 1
for _ in range(max_digit + 1):
  a = A % 2
  c = np.count_nonzero(a == 0)
  result = (result + (base*(N - c)*c) % mod) % mod
  A = A >> 1
  base *= 2

print(result)
n=int(input())
a=list(map(int,input().split()))
c=[0]*n
c[0]=3
cnt=1
for i in a:
  cnt=cnt*c[i]%1000000007
  c[i]-=1
  c[i+1]+=1

print(cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
c=[0]*(n+1)
c[0]=3
cnt=1
for i in a:
  cnt=cnt*c[i]%1000000007
  c[i]-=1
  c[i+1]+=1
print(cnt)
a = int(input())
b = int(input())
c = int(input())

print("c"),
print("a"),
print("b"),

### FIXED CODE ###

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

print(c,a,b)
while True:
    n = 1
    if input() == 0:
        break
    print("Case " + n + ": " + str(input()))
    n+=1


### FIXED CODE ###

i = 1

while True:
    x = int(input())
    if x == 0:
        break
    print("Case " + str(i) + ": " + str(x))
    i += 1
def gcd(a,b):
	if a==0:
		return b
	return gcd(b%a,a)

def find_lcm(num1, num2):
    if(num1>num2):
        b = num1
        a = num2
    else:
        b = num2
        a = num1
    G = gcd(a,b)
    lcm = int(int(num1 * num2)/int(G))
    return lcm
     
N=int(input())
A=list(map(int,input().split()))
lcm = find_lcm(A[0],A[1])
for I in range(2, N):
    lcm = find_lcm(lcm, A[I])
Ans=0
lcm-=1
for I in range(N):
	Ans+=(lcm%A[I])
print(Ans)

### FIXED CODE ###

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

def find_lcm(num1, num2):
    if(num1>num2):
        b = num1
        a = num2
    else:
        b = num2
        a = num1
    G = gcd(a,b)
    lcm = (num1*num2)//G
    return lcm
     
N=int(input())
A=list(map(int,input().split()))
lcm = find_lcm(A[0],A[1])
for I in range(2, N):
    lcm = find_lcm(lcm, A[I])
Ans=0
lcm-=1
for I in range(N):
	Ans+=(lcm%A[I])
print(Ans)
a = input().split()
b = input().split()
c = input().split()
list_ans =(a,b,c)
N = int(input())
bingo_list=[]

for i in range(N):
    bingo = input()
    bingo_list.append(bingo)
    
#横ビンゴ判定
def bingo_row(p,q):
    #p 横のリスト　q 出た値のリスト
    for i in range(3):
        if p[i] in q:
            return True
        else:
            return False
#縦ビンゴ判定
def bingo_column(p,q,r,s):
    batu = 0
    #pqr横リスト　s bingo_list
    for i in range(4):
        
        if p[i]  in s and q[i] in s:
            if r[i] in s:
                return True
                break
            else:
                batu +=1 
        else:
            batu +=1
    if batu == 3:
        return False
#斜めビンゴ判定
def bingo_slash(p,q,r,s):
    if q[1] in s:
        if p[0] in s and r[2] in s:
            return True
        elif p[2] in s and r[0] in s:
            return True
        else:
            return False
    else:
        return False

    
total = 0
for i in list_ans:
    if bingo_row(i, bingo_list):
        print('Yes')
        break
    elif bingo_column(a,b,c,bingo_list):
        print('Yes')
        break
    elif bingo_slash(a,b,c,bingo_list):
        print('Yes')
        break
    else:
        total += 1
if total == 3:
    print('No')

### FIXED CODE ###

a = input().split()
b = input().split()
c = input().split()
list_ans =(a,b,c)
N = int(input())
bingo_list=[]

for i in range(N):
    bingo = input()
    bingo_list.append(bingo)


#横ビンゴ判定
def bingo_row(p,q):
    row_total= 0
    #p 横のリスト　q 出た値のリスト
    for i in range(3):
        if p[i] in q:
            row_total +=1
        else:
            return False
    if row_total == 3:
        return True
#縦ビンゴ判定
def bingo_column(p,q,r,s):
    batu = 0
    #pqr横リスト　s bingo_list
    for i in range(3):
        
        if p[i]  in s and q[i] in s:
            if r[i] in s:
                return True
                break
            else:
                batu +=1 
        else:
            batu +=1
    if batu == 3:
        return False
#斜めビンゴ判定
def bingo_slash(p,q,r,s):
    if q[1] in s:
        if p[0] in s and r[2] in s:
            return True
        elif p[2] in s and r[0] in s:
            return True
        else:
            return False
    else:
        return False

    
total = 0
for i in list_ans:
    if bingo_row(i, bingo_list):
        print('Yes')
        break
    elif bingo_column(a,b,c,bingo_list):
        print('Yes')
        break
    elif bingo_slash(a,b,c,bingo_list):
        print('Yes')
        break
    else:
        total += 1
if total == 3:
    print('No')
# -*- coding:utf-8 -*-
import sys
N = int(input())
s = sorted([ int(input()) for tmp in range(N) ])
total = sum(s)
if total%10 != 0:
    print(total)
else:
    for tmp in s:
        total -= tmp
        if total%10 != 0:
            print(total)
            sys.exit()
        else:
            pass
    print(0)
[Shellingford:

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys
N = int(input())
s = []
for tmp in range(N):
    s.append(int(input()))
s.sort()
total = sum(s)
if total%10 != 0:
    print(total)
else:
    for tmp in s:
        total -= tmp
        if total%10 != 0:
            print(total)
            sys.exit()
        else:
            total += tmp
    print(0)
import collections
N,M = map(int,input().split())
edge = collections.defaultdict(list)
for _ in range(M):
    u,v = map(int,input().split())
    edge[u-1].append(v-1)
S,T = map(int,fi.input().split())
dp = [-1 for _ in range(N)]
dp[S-1] = 0
q = collections.deque()
q.append(S-1)
while q:
    p = q.pop()
    for k1 in edge[p]:
        for k2 in edge[k1]:
            for k3 in edge[k2]:
                if dp[k3] == -1:
                    dp[k3] = dp[p] + 1
                    q.append(k3)
                    if k3 == T-1:
                        break
print(dp[T-1])

### FIXED CODE ###

import collections
N,M = map(int,input().split())
edge = collections.defaultdict(list)
for _ in range(M):
    u,v = map(int,input().split())
    edge[u-1].append(v-1)
S,T = map(int,input().split())
dp = [[-3 for _ in range(3)] for _ in range(N)]
dp[S-1][0] = 0
q = collections.deque()
q.append((S-1,0))
while q:
    p,step = q.popleft()
    next_step = (step+1)%3
    for e in edge[p]:
        if dp[e][next_step] == -3:
            dp[e][next_step] = dp[p][step] + 1
            q.append((e,next_step))
            if e == T-1 and next_step == 0:
                break
print(dp[T-1][0] // 3)
# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = input()
        # print(len(k))
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        pre = [[0] * (d + 1) for _ in range(s + 1)]
        for i in range(d):
            pre[1][i] = pre[1][i - 1] + dp[1][i]
        for l in range(2, s):
            # cur is sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)
            cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            for r in range(d):
                # print(l, r)
                # lo, hi = min((r - 1) % d, (r - 9) % d), max((r - 1) % d, (r - 9) % d)
                # assert((pre[l - 1][hi] - pre[l - 1][lo - 1]) == sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)))
                # dp[l][r] = (dp[l - 1][r] + (pre[l - 1][hi] - pre[l - 1][lo - 1])) % MOD
                dp[l][r] = (dp[l - 1][r] + cur) % MOD
                cur -= dp[l - 1][(r - 9) % d]
                cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = input().strip()
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        pre = [[0] * (d + 1) for _ in range(s + 1)]
        for i in range(d):
            pre[1][i] = pre[1][i - 1] + dp[1][i]
        for l in range(2, s):
            # cur is sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)
            cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            for r in range(d):
                # dp[l][r] = (dp[l - 1][r] + sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10))) % MOD
                dp[l][r] = (dp[l - 1][r] + cur) % MOD
                cur -= dp[l - 1][(r - 9) % d]
                cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()
s = str(input())
t = str(input())
print(t + s)

### FIXED CODE ###

i = str(input()).split(" ")
print(i[1] + i[0])
def needed_to_flip(c):
    return ord('z') - ord(c) + 1

s = list(raw_input())
K = int(raw_input())
#s = list('za')
#K = 4


for i, c in enumerate(s):
	if c == 'a':
		continue
	needed = needed_to_flip(c)
	#print "%s: needed: %d, has: %d" % (c, needed, K)
	if K >= needed:
		K -= needed
		s[i] = 'a'
		
	#print "flip: %s needed: %d, has: %d" % (s[i], needed,K) 
	if i == len(s) - 1:
		s[i] = chr(ord(s[i]) + (K % 26))

print ''.join(s)
 




### FIXED CODE ###

s = raw_input()

print "%s %s" % (s[:4], s[4:])
import itertools
import numpy as np

if __name__ == "__main__":

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

	# print(P)
	# 一度計算したサイクル情報をキャッシュしておくための配列
	cycleIDs = np.full( N, -1, np.int64 )
	cycleInfs = []
	cycleID = 0
	procCnt = 0

	for n in range(N):
		v = n

		if cycleIDs[v] != -1:
			continue
		else:
			currentCycleCosts = []
			while True:
				# 全頂点について、属するサイクルを計算する
				currentCycleCosts.append( C[v] )
				cycleIDs[v] = cycleID

				v = P[v]
				if cycleIDs[v] != -1:
					# サイクル終了
					# ループを含めない最大の処理回数
					procCnt = K % len( currentCycleCosts )
					# ただし、割り切れる場合も、1サイクル分は処理するものとする
					# (1回以上はやらなければならないのを考慮？)
					if procCnt == 0:
						procCnt = len( currentCycleCosts )

					cycleInfs.append( ( procCnt, np.array( currentCycleCosts ) ) )
					cycleID += 1
					break



	scores = []
	# loopScore = 0
	# procCnt = 0
	for procCnt, currentCycleCosts in cycleInfs:

		# サイクル内でループしてスコアを稼ぐ場合の考慮
		# if np.sum(currentCycleCosts) > 0:
		# 	cycleLoopCnt =  ( K - procCnt ) // currentCycleCosts.size
		# 	loopScore = cycleLoopCnt * np.sum(currentCycleCosts)

		# このサイクルに属する全頂点分をまとめて計算する
		for i in range(currentCycleCosts.size):
			if np.sum(currentCycleCosts) > 0:
				# acc = list(itertools.accumulate( np.roll( currentCycleCosts, i )[:procCnt] ) )
				scores.append( np.roll( currentCycleCosts, i )[:procCnt].cumsum().max() ) + (( K - procCnt ) // currentCycleCosts.size) * np.sum(currentCycleCosts) )
			else:
				scores.append( np.roll( currentCycleCosts, i )[:procCnt].cumsum().max() )


	print(max(scores))


### FIXED CODE ###

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

if __name__ == "__main__":

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

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


	# print(P)

	ans = -1e10
	cycleID = 0

	for n in range(N):

		v = n
		currentCycleItemCnt = 0
		currentCycleTotal = 0

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

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

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

		procCnt = 0
		currentCycleSumTmp = 0

		while True:

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

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

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

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

	print(ans)
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #C
    #input
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
     
    #output
    #A[i]の電球は i-A[i] から i+A[i]までを照らす。
    import numpy as np  
    K = min(K, 42)
    for _ in range(K):
        dp = np.zeros(N, int)
        for i in range(N):
            p = max(0, i-A[i])
            dp[p] += 1
            if i+A[i]+1 <= N-1:
                dp[i+A[i]+1] -= 1
        dp = np.cumsum(dp)
        A = dp
     
    print(" ".join(repr(d) for d in dp))    

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()


### FIXED CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #C
    #input
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
     
    #output
    #A[i]の電球は i-A[i] から i+A[i]までを照らす。
    import itertools
    K = min(K, 42)
    for _ in range(K):
        dp = [0]*N
        for i in range(N):
            p = max(0, i-A[i])
            dp[p] += 1
            if i+A[i]+1 <= N-1:
                dp[i+A[i]+1] -= 1
        dp = list(itertools.accumulate(dp))
        A = dp
     
    print(" ".join(repr(d) for d in dp))

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()
n,m = map(int,input().split())
s=[0]*m
c=[0]*m
ans=[]
judge=False
for i in range(m):
    s[i],c[i]=map(int,input().split())
for j in range(10**(n-1)-1,10**n):
    j=str(j)
    for l in range(m):
        if int(j[s[l]-1])==c[l]:
            pass
        else:
            break
    else:
        ans.append(int(j))
        judge=True
if judge:
    print(min(ans))
else:
    print('-1')

### FIXED CODE ###

N,M=map(int,input().split())
s=[]
c=[]
for i in range(M):
    a,b=map(int,input().split())
    s.append(a)
    c.append(b)
found=False
start=pow(10,N-1)
stop=pow(10,N)
if N==1:
    start=0
for i in range(start,stop):
    i_str=str(i)
    passed=True
    for j in range(M):
        if not i_str[s[j]-1]==str(c[j]):
            passed=False
            break
    if passed:
        found=True
        print(i)
        break
if not found:
    print('-1')
import sympy

A, B, K = map(int, input().split())

set_a = set(sympy.divisors(A))
set_b = set(sympy.divisors(B))
# print(f'set_a ({A}): {set_a}')
# print(f'set_b ({B}): {set_b}')

set_ab = set_a.intersection(set_b)

list_ab = list(set_ab)
list_ab.sort()
# print(list_ab)

print(list_ab[K - 1])

### FIXED CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

A, B, K = map(int, input().split())

set_a = set(make_divisors(A))
set_b = set(make_divisors(B))
set_ab = set_a.intersection(set_b)

list_ab = list(set_ab)
list_ab.sort()
# print(list_ab)

print(list_ab[-K])
A, B = map(int, input())

print(max([A + B, A - B, A * B]))


### FIXED CODE ###

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

print(max([A + B, A - B, A * B]))
# input
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

# 考え方
# 目標：最大値の最小化
# にぶたん
# 必要条件：A[i] <= A[i+1] => F[i] >= F[i+1]

# sort
# Aは昇順、Fは降順(任意)
A = sorted(A)
F = sorted(F, reverese=True)

# にぶたん(参考：juppy)
ng = -1
ok = 10 ** 12  # 取り得る最大値

while ok - ng > 1:  # 収束判定
    mid = (ok + ng) // 2
    cost = 0

    for i, e in enumerate(A):
        cost += max(0, e - mid // F[i])
    
    if cost <= K:
        ok = mid
    
    else:
        ng = mid

print(ok)

### FIXED CODE ###

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

# 考え方
# 目標：最大値の最小化
# にぶたん
# 必要条件：A[i] <= A[i+1] => F[i] >= F[i+1]

# sort
# Aは昇順、Fは降順(任意)
A = sorted(A)
F = sorted(F, reverse=True)

# にぶたん(参考：juppy)
ng = -1
ok = 10 ** 12  # 取り得る最大値

while ok - ng > 1:  # 収束判定
    mid = (ok + ng) // 2
    cost = 0

    for i, e in enumerate(A):
        cost += max(0, e - mid // F[i])
    
    if cost <= K:
        ok = mid
    
    else:
        ng = mid

print(ok)
a=input()
b=input()
c={}
state=True
for i in range(len(a)):
  if (b[i] not in c) and (a[i] not in c):
    c[b[i]]=a[i]
    c[a[i]]=b[i]
  if c[b[i]]!=a[i]:
    state=False
if state:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a=input()
b=input()
c={}
state=True
for i in range(len(a)):
  if b[i] not in c and a[i] not in c.values():
    c[b[i]]=a[i]
  if b[i] in c:
    if c[b[i]]!=a[i]:
      state=False
  else:
    state=False
if state:
  print('Yes')
else:
  print('No')
result=0
while count<=a:
	if a<=1:
		result += n+1
		break
	else:
		if count==a:
			result += n-10**count + 1
			count += 2
		else:
			if  count==0:
				result+=10
				count +=2
			else:
				result += 10**(count+1)-10**count
				count += 2
print(result-1)

### FIXED CODE ###

n=int(input())
re=0
for i in range(1,n+1):
  if len(str(i))%2==1:
    re+=1
print(re)
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    # ABC174-F

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

    Bsize = int(N ** 0.5) + 1
    query = []
    for q in range(Q):
        l, r = map(int, input().split())
        query.append((l - 1, r - 1, q))
    query.sort(key=lambda x: x[1])
    query.sort(key=lambda x: x[3] // Bsize)
    exit()

    # [l, r)での求める値を管理するための変数たち
    # 問題によって変える
    cnt = [0] * (N + 1)
    val = 0

    # 区間の伸縮操作
    # 問題によって変える
    def add(i):
        global val
        cnt[A[i]] += 1
        if cnt[A[i]] == 1:
            val += 1

    def rem(i):
        global val
        cnt[A[i]] -= 1
        if cnt[A[i]] == 0:
            val -= 1

    # init
    l, r, _ = query[0]
    for i in range(l, r + 1):
        add(i)

    # process
    ans = [0] * Q
    for l_new, r_new, q in query:
        if r < r_new:
            for i in range(r + 1, r_new + 1):
                add(i)
        elif r > r_new:
            for i in range(r, r_new, -1):
                rem(i)
        if l < l_new:
            for i in range(l, l_new):
                rem(i)
        elif l > l_new:
            for i in range(l - 1, l_new - 1, -1):
                add(i)
        l = l_new
        r = r_new
        ans[q] = val

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    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

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    query = []
    for q in range(Q):
        query.append(list(map(int, input().split())))
        query[-1].append(q)
    query.sort(key=lambda x: x[1])

    last = [0] * (N+1)
    for i, c in enumerate(C):
        if i > query[0][1]-1:
            break
        last[c] = i+1

    bit = Bit(N)
    for i in range(1, N+1):
        if last[i]:
            bit.add(last[i], 1)
    r_prev = query[0][1]
    ans = [0] * Q
    for l, r, q in query:
        if r > r_prev:
            for i in range(r_prev+1, r+1):
                j = last[C[i-1]]
                if j:
                    bit.add(j, -1)
                last[C[i-1]] = i
                bit.add(i, 1)
            r_prev = r
        ans[q] = bit.sum(r) - bit.sum(l-1)

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()
n = input()
aa = []
xx = [-input()]
for _ in xrange(n - 1):
    aa.append(-input())
for a in aa:
    if a >= xx[-1]:
        xx.append(a)
    else:
        i = bisect.bisect_right(xx, a)
        if i == len(xx):
          i -= 1
        xx[i] = a
print len(xx)

### FIXED CODE ###

import bisect
n = input()
aa = []
xx = [-input()]
for _ in xrange(n - 1):
    aa.append(-input())
for a in aa:
    if a >= xx[-1]:
        xx.append(a)
    else:
        i = bisect.bisect_right(xx, a)
        if i == len(xx):
          i -= 1
        xx[i] = a
print len(xx)