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

import numpy as np
import time

n = input()

#空のリストを作成
fizzbuzz_list = 0

#3の倍数のリストを作成
multiples_of_3 = np.arange(3, 9*int(len(n))+1, 3)

def digitsum(n):
    # 数値を文字列に変換
    s = str(n)
    # １文字ずつ数値化し配列にする。
    array = list(map(int, s))
    # 合計値を返す
    return sum(array)

def place_of_one(n):
    # 数値を文字列に変換
    s = str(n)
    # １文字ずつ数値化し配列にする。
    array = list(map(int, s))
    # 1の位を返す
    return array[-1]

def dt_mu_15(n):
    if place_of_one(n) == 0 or place_of_one(n) == 5:
        if digitsum(n) in multiples_of_3:
            return n
    else: 
        pass

# start = time.time()

for i in range(int(n)):
    if dt_mu_15(i+1):
          pass
    elif digitsum(i+1) in multiples_of_3:
         pass
    elif place_of_one(i+1) == 0 or place_of_one(i+1) == 5 :
         pass
    else:
         fizzbuzz_list += (i+1)

# end = time.time()
# print(end-start)

print(fizzbuzz_list)



### FIXED CODE ###


N = int(input())

total = 0

for i in range(N):

    if (i+1) % 15 == 0:
        pass
    elif (i+1) % 3 == 0:
        pass
    elif (i+1) % 5 == 0:
        pass
    else:
        total += (i+1)
        
print(total)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    A, B, C, D = [int(x) for x in input().split()]

    MOD = 998244353

    dp = [[0] * (D - B + 1) for j in range(C - A + 1)]

    for j in range(C - A + 1):
        if j == 0:
            dp[j][0] = 1
        else:
            dp[j][0] = B ** j
        for i in range(1, D - B + 1):
            if j == 0:
                dp[j][i] = dp[j][i - 1] * (A + j)
            else:
                dp[j][i] = dp[j][i - 1] * (A + j) + (B + i) * dp[j - 1][i] - dp[j - 1][i - 1] * (
                            (A + j - 1) * (B + i - 1))

    print(dp[-1][-1] % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    A, B, C, D = [int(x) for x in input().split()]

    MOD = 998244353

    dp = [[0] * (D - B + 1) for j in range(C - A + 1)]

    for j in range(C - A + 1):
        if j == 0:
            dp[j][0] = 1
        else:
            dp[j][0] = pow(B, j, MOD)
        for i in range(1, D - B + 1):
            if j == 0:
                dp[j][i] = dp[j][i - 1] * (A + j) % MOD
            else:
                dp[j][i] = (dp[j][i - 1] * (A + j) + (B + i) * dp[j - 1][i] - dp[j - 1][i - 1] * (
                            (A + j - 1) * (B + i - 1))) % MOD

    print(dp[-1][-1] % MOD)


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

from functools import reduce
from fractions import gcd
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

n = int(input())
A = [int(i) for i in input().split()]
k = lcm_list(A)
r = 0
for i in range(n):
    r += k//A[i]
    if r > 10**9+7:
        r %= 10**9+7
print(r)

### FIXED CODE ###

from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

n = int(input())
A = list(map(int, input().split()))
k = lcm_list(A)
r = 0
ln = list(range(n))
for i in ln:
    r += k//A[i]
print(r%(10**9+7))
### BUGGY CODE ###

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

ans = 0
for i in range(n-k+1):
    ans = max(ans,sum(p[i:i+k]))

print(0.5+(0.5*ans)+(k-1)*0.5)

### FIXED CODE ###

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

wrk = sum(p[:k])
ans = wrk
for i in range(1,n-k+1):
    wrk-=p[i-1]
    wrk+=p[i+k-1]
    ans = max(ans,wrk)

print(0.5+(0.5*ans)+(k-1)*0.5)
### BUGGY CODE ###

N=int(input())
S=[i for i in input()]
ans=float('inf')
for i in range(N):
    l=S[:i]
    r=S[i+1:]
    E_change=l.count('W')
    W_change=r.count('E')
    ans=min(E_change+W_change,ans)
print(ans)

### FIXED CODE ###

# coding: utf-8
#累積和
N=int(input())
S=[i for i in input()]

pls_E=[0]*N
pls_W=[0]*N

#初期値
if S[N-1]=='E':
    pls_E[N-1]=1
else:
    pls_E[N-1]=0
    
if S[0]=='W':
    pls_W[0]=1
else:
    pls_W[0]=0

#Wの累積和(左から)
for i in range(1,N):
    if S[i]=='W':
        pls_W[i]=pls_W[i-1]+1
        
    else:
        pls_W[i]=pls_W[i-1]

#Eの累積和（右から）
for i in range(N-2,-1,-1):
    if S[i]=='E':
        pls_E[i]=pls_E[i+1]+1
    else:
        pls_E[i]=pls_E[i+1]

#print(pls_W,pls_E)
ans=float('inf')
for i in range(1,N-1):
    ans=min(ans,pls_W[i-1]+pls_E[i+1])
    
print(min(ans,pls_E[1],pls_W[N-2]))
### BUGGY CODE ###

n = int(input())
l = [input() for i in range(n)]

mylist = []
for s in l:
    s_list = [ c for c in s]
    mylist.append("".join(sorted(s_list)))

myset = set(mylist)
mylist2 = list(myset)

ans=0
for i in range(len(mylist2)):
    count = mylist.count(mylist2[i])
    mylist3 = list(range(count))
    ans += sum(mylist3)

print(ans)


### FIXED CODE ###

n = int(input())
i = 0
sortedSet = {}
while i < n:
    temp = ''.join(sorted(input()))

    if temp in sortedSet:
        sortedSet[temp]+=1
    else:
        sortedSet[temp]=1
    i += 1

result = 0
for v in sortedSet.values():
    result = int(result + v*(v-1)/2)

print(result)
### BUGGY CODE ###

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

ans = 0
for i in range(N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        for c in L[j+1:]:
            if a < b+c and b < a+c and c < a+b:
                ans += 1
print(ans)

### FIXED CODE ###

import bisect
    
N = int(input())
L = sorted(list(map(int, input().split())))
    
ans = 0
for i in range(N):
    for j in range(i+1, N):
        index = bisect.bisect_left(L, L[i]+L[j])
        ans += index - 1 - j
print(ans)
### BUGGY CODE ###

list_S = list(input())
k = int(input())
set_ANS = set()
list_Alph = list(set(list_S))
list_Alph.sort()
cnt = 0

for c in list_Alph:
    q = [i for i, x in enumerate(list_S) if x == c]
    for j in range(1, len(list_S)+1):
        for i in q:
            if i + j <= len(list_S):
                l = "".join(list_S[i:i+j])
                if l not in set_ANS:
                    set_ANS.add(l)
                    cnt += 1
    if cnt >= k:
        list_ANS = list(set_ANS)
        list_ANS.sort()
        print(list_ANS[k-1])
        exit()

### FIXED CODE ###

list_S = list(input())
k = int(input())
set_ANS = set()
list_Alph = list(set(list_S))
cnt = 0
list_Alph.sort()

for c in list_Alph:
    q = [i for i, x in enumerate(list_S) if x == c]
    list_M = []
    for i in q:
        l = "".join(list_S[i:])
        list_M.append(l)
    list_M.sort()
    for s in list_M:
        m = list(s)
        for j in range(1,len(m)+1):
            b = "".join(m[:j])
            if b not in set_ANS:
                set_ANS.add(b)
                cnt += 1
                if cnt == k:
                    print(b)
                    exit()
### BUGGY CODE ###

s = input()

complete = False
ans = 0

while complete == False:
    complete = True
    i = 0
    while i < len(s) - 1:
        if s[i] != s[i+1]:
            s = s[:i] + s[i+2:]
            ans = ans + 2
            complete = False
        i = i + 1

print(ans)

### FIXED CODE ###

s = input()

one = s.count("1")
zero = s.count("0")

print(2 * min(one, zero))
### BUGGY CODE ###

N,Q = map(int, input().split())
S = input()
ans = []
for i in range(Q):
    l,r = map(int, input().split())
    S_ = S[l-1:r]
    ans.append(S_.count("AC"))
print(*ans, sep="\n")

### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
count = [0]*N
for i in range(1,N):
    count[i] += count[i-1]
    if S[i-1:i+1] == "AC":
        count[i] += 1
for i in range(Q):
    l,r = map(int, input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

n,k = map(int,input().split())
a = [int(i) - 1 for i in input().split()]
r = []
nx = 0
for i in range(n):
    r.append(nx)
    if k < i:
        print(r[k] + 1)
        break
    if a[nx] in r:
        m = r.index(a[nx])
        d = i - m + 1
        k = k - m
        k = k % d
        print(r[k + m] + 1)
        break  
    nx = a[nx]


### FIXED CODE ###

n,k = map(int,input().split())
a = [int(i) - 1 for i in input().split()]
r = []
nx = 0
sr = set([])
for i in range(n):
    r.append(nx)
    sr.add(nx)
    if k < i:
        print(r[k] + 1)
        break
    tnx = a[nx]
    if tnx in sr:
        m = r.index(a[nx])
        d = i - m + 1
        k = k - m
        k = k % d
        print(r[k + m] + 1)
        break  
    nx = tnx
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
	
	class BinaryIndexedTree:
		
		# 初期化
		def __init__(self, size, default):
			self.size = size
			self.default = default
			self.BIT = [default]*(self.size+1)

		# function(max, min, plus, minus, etc...)
		def BIT_segfunc(self, x, y):
			return max(x, y)

		def BIT_query(self, idx):
			ret = self.default
			while idx > 0:
				ret = self.BIT_segfunc(ret, self.BIT[idx])
				idx -= idx&(-idx)
			return ret

		# update
		def BIT_update(self, idx, x):
			while idx <= self.size:
				self.BIT[idx] = self.BIT_segfunc(self.BIT[idx], x)
				idx += idx&(-idx)
			return

		def BIT_range(self, x, y):
			return self.BIT_query(y)-self.BIT_query(x)

		# seg確認用
		def BIT_print(self):
			print(self.BIT)
		
	N = int(input())
	a = list(map(int,input().split()))
	ans=[i+1 for i in range(N)]
	left_bit = BinaryIndexedTree(N, 0)
	for i, num in enumerate(a):
	    ans[num-1] *= i + 1 - left_bit.BIT_query(num)
	    left_bit.BIT_update(num, i+1)
	right_bit = BinaryIndexedTree(N, 0)
	for i, num in enumerate(a[::-1]):
	    ans[num-1] *= i + 1 - right_bit.BIT_query(num)
	    right_bit.BIT_update(num, i+1)
	
	print(sum(ans))

if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
	
	class BinaryIndexedTree:
		
		# 初期化
		def __init__(self, size, default):
			self.size = size
			self.default = default
			self.BIT = [default]*(self.size+1)

		# function(max, min, plus, minus, etc...)
		def BIT_segfunc(self, x, y):
			return max(x, y)

		def BIT_query(self, idx):
			ret = self.default
			while idx > 0:
				ret = self.BIT_segfunc(ret, self.BIT[idx])
				idx -= idx&(-idx)
			return ret

		# update
		def BIT_update(self, idx, x):
			while idx <= self.size:
				self.BIT[idx] = self.BIT_segfunc(self.BIT[idx], x)
				idx += idx&(-idx)
			return

		def BIT_range(self, x, y):
			return self.BIT_query(y)-self.BIT_query(x)

		# seg確認用
		def BIT_print(self):
			print(self.BIT)
		
	N = int(input())
	a = list(map(int,input().split()))
	l = [0]*N;r = [0]*N
	left_bit = BinaryIndexedTree(N, 0)
	for i, num in enumerate(a):
	    l[num-1] = i + 1 - left_bit.BIT_query(num)
	    left_bit.BIT_update(num, i+1)
	right_bit = BinaryIndexedTree(N, 0)
	for i, num in enumerate(a[::-1]):
	    r[num-1] = i + 1 - right_bit.BIT_query(num)
	    right_bit.BIT_update(num, i+1)
	
	print(sum(l[i]*r[i]*(i+1) for i in range(N)))

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

string = input()
for i in range(int(input())):
	Q = input()
	if Q[0] == '1':
		string = string[::-1]
	else:
		T,F,C = Q.split(' ')
		if F == '1':
			string = C + string
		elif F == '2':
			string += C
print(string)


### FIXED CODE ###

string = input()
N=int(input())
Que = []
for i in range(N):
	Que.append(input())

init = ""
end = ""
rev = 2
for Q in Que:	
	if int(Q[0]) == 1:
		if rev != 1:
			rev=1
		else:
			rev=2
	elif int(Q[0])==2:
		T,F,C = Q.split(' ')
		if rev == 1:
			if int(F) == 1:
				F =2
			else:
				F = 1
		if int(F) == 1:
			init = init+C
		elif int(F) == 2:
			end = end + C
final = init[-1::-1]+string+end
if rev == 1:
	print(final[-1::-1])
else:
	print(init[-1::-1]+string+end)
### BUGGY CODE ###

a, b = input().split()
a = int(a)
b = int(b)
ans = -1
for i in range(1000000000000000000):
    if (a * i) % b != 0:
        ans = a * i
        break
print(ans)

### FIXED CODE ###

a, b = input().split()
a = int(a)
b = int(b)
ans = -1
for i in range(1000000000000000000):
    if a % b == 0:
        break
    if a*i > 1000000000000000000:
        break
    if (a * i) % b != 0:
        ans = a * i
        break
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
s = [0 for i in range(n+1)]
for i in range(n):
    s[i+1] = s[i] + a[i]
t = list(set(s))

def comb(n, r):
    a = 1
    for i in range(n-r+1, n+1):
        a *= i
    for i in range(1, r+1):
        a //= i
    return a

for i in t:
    m = s.count(i)
    ans += comb(m, 2)
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
ans = 0
s = [0]
for i in range(n):
    s.append(s[i] + a[i])

t = Counter(s).most_common()

def comb(n, r):
    a = 1
    for i in range(n-r+1, n+1):
        a *= i
    for i in range(1, r+1):
        a //= i
    return a

for p in t:
    ans += comb(p[1], 2)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

d,g = LI()
pc = [LI() for _ in range(d)]
ans = inf
for i in permutations(range(d)):
    cnt = 0
    tmp = 0
    for j in list(i):
        flg = (g-tmp) % (100*(j+1))
        t = min(pc[j][0],(g - tmp)//(100*(j+1)))
        tmp += 100*(j+1)*t
        if t == pc[j][0]:
            tmp += pc[j][1]
            cnt += t
            if tmp >= g:
                break
        else:
            cnt += t + (flg != 0)
            break
    ans = min(ans,cnt)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import numpy as np
import math
import re

a,b=map(int,input().split())
c=[0]+[list(map(int,input().split()))for i in range(a)]

def f(t,s):
    if t==0:
        return 10**9
    l=min(s//(t*100),c[t][0])
    k=100*t*l
    if l==c[t][0]:
        k+=c[t][1]
    if k<s:
        l+=f(t-1,s-k)
    return min(l,f(t-1,s))
print(f(a,b))
### BUGGY CODE ###

def chmin(a, b):
    if b < a:
        a = b
    return a

nums, jump = list(map(int, input().split()))
height = list(map(int,input().split()))
dp = [0 for i in range(nums)]
for i in range(nums):dp[i] = float("inf")
dp[0] = 0

for i in range(nums):
    for x in range(1,jump+1):
        if i+x >= nums: continue
        dp[i+x] = chmin(dp[i+x],dp[i] + abs(height[i] - height[i+x]))

print(dp[nums-1])

### FIXED CODE ###

import numpy as np

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

h = np.array(h)
dp = np.zeros(n, dtype=int)

for i in range(1,n):
    m = max(0,i-k)
    dp[i] = min(dp[m:i] + np.abs(h[i] - h[m:i]))
print(dp[n-1])
### BUGGY CODE ###

import copy

N = int(input())
S = [list(input()) for _ in range(N)]
S = copy.copy(S) + copy.copy(S)
ans = 0

for A in range(N):
    sym = True
    for i in range(N):
        for j in range(i+1, N):
            if S[i+A][j] != S[j+A][i]:
                sym = False
                break
        else:
            continue
        break
    if sym:
        ans += N

print(ans)

### FIXED CODE ###

N = int(input())
S = [list(input()) for _ in range(N)]
#N = 300
#S = [["a"]*N for _ in range(N)]
ans = 0

for A in range(N):
    if all([S[(i+A)%N][j] == S[(j+A)%N][i] for i in range(N) for j in range(i+1, N)]):
        ans += N
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
li_h = list(map(int, input().split()))
li_route = list()
remove_idx_set = set()

for _ in range(m):
    a, b = map(int, input().split())

    h_a = li_h[a - 1]
    h_b = li_h[b - 1]

    if h_a <= h_b:
        if h_a in li_h:
            remove_idx_set.add(a - 1)
    if h_a >= h_b:
        if h_b in li_h:
            remove_idx_set.add(b - 1)
for s in remove_idx_set:
    li_h[s] = 0
print(len([v for v in li_h if v != 0]))


### FIXED CODE ###

n, m = map(int, input().split())
li_h = list(map(int, input().split()))
li_route = list()
remove_idx_set = set()

for _ in range(m):
    a, b = map(int, input().split())

    h_a = li_h[a - 1]
    h_b = li_h[b - 1]

    if h_a <= h_b:
        remove_idx_set.add(a - 1)
    if h_a >= h_b:
        remove_idx_set.add(b - 1)
for s in remove_idx_set:
    li_h[s] = 0
print(len([v for v in li_h if v != 0]))
### BUGGY CODE ###

D, N = map(int, input().split())
cnt = 0
n = 1
a = 10**D
while True:
  if n % a == 0 and n % (a * 100) == 0:
    cnt += 1
    if cnt == N:
      print(n)
      exit()

### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(D: int, N: int):
    if N == 100:
        print((100**D)*101)
    else:
        print((100**D)*N)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    D = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    solve(D, N)

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

N = int(input())
A = [int(i) for i in input().split(" ")]
Q = int(input())
for i in range(Q):
    B,C = map(int,input().split(" "))
    A = [C if i == B else i for i in A]
    print(sum(A))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = [int(i) for i in input().split(" ")]
count = Counter(A)
S = sum(A)
Q = int(input())
for i in range(Q):
    B,C = map(int,input().split(" "))
    n = count[B]
    count[B] -= n
    count[C] += n
    S = S - B*n + C*n
    print(S)
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))

def get_ans(a):
    mods = list()
    
    if 2 not in a:
        print(-1)
        return True
    
    count = 0
    mod = 1
    while(True):
        mod = a[mod-1]
        count += 1
        if (mod == 2):
            print(count)
            return True
        elif mod in mods:
            print(-1)
            return True
        else:
            mods.append(mod)

ret = get_ans(a)

### FIXED CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input())-1)
index = 0
#indexが1になったら（２ボタンを押したら）おしまい
flag = False 
count = 0
for i in range(N):
    count+=1
    index=a[index]
    if(index == 1):
        flag = True
        break
if(flag):
    print(count)
else:
    print(-1)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve: #区間[2,n]の値の素因数分解
    def __init__(self,n=1):
        self.primes=[]
        self.f=[0]*(n+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        for i in range(2,n+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,n+1,i):
                if not self.f[j]:
                    self.f[j]=i  # 最小の素因数を代入
    def is_prime(self, x):
        return self.f[x]==x
    def prime_fact(self,x): # 素因数分解の昇順リスト, {2:p,3:q,5:r,...}
        self.fact_dict=dict()
        while x!=1:
            p=self.f[x]
            self.fact_dict[p]=self.fact_dict.get(p,0)+1
            x//=self.f[x]
        return self.fact_dict

def main():
    n=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    p_lis={}
    p_a_lis=[]
    Prime=Sieve(max(A))
    for a in A:
        p_a_lis.append(Prime.prime_fact(a))
        for key in p_a_lis[-1]:
            if not p_lis.get(key,False) or p_lis[key]<p_a_lis[-1][key]:
                p_lis[key]=p_a_lis[-1][key]
    ans=0
    for i,a in enumerate(A):
        b=1
        for key in p_lis:
            b*=(key**(p_lis[key]-p_a_lis[i].get(key,0)))%mod
        ans=(ans+b)%mod
    print(ans)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve: #区間[2,n]の値の素因数分解
    def __init__(self,n=1):
        self.primes=[]
        self.f=[0]*(n+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        for i in range(2,n+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,n+1,i):
                if not self.f[j]:
                    self.f[j]=i  # 最小の素因数を代入
    def is_prime(self, x):
        return self.f[x]==x
    def prime_fact(self,x): # 素因数分解の昇順リスト, {2:p,3:q,5:r,...}
        fact_dict=dict()
        while x!=1:
            p=self.f[x]
            fact_dict[p]=fact_dict.get(p,0)+1
            x//=self.f[x]
        return fact_dict

def main():
    n=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    p_lis={}
    Prime=Sieve(10**6+5)
    for a in A:
        f=Prime.prime_fact(a)
        #print(f)
        for key in f:
            p_lis[key]=max(p_lis.get(key,0),f[key])
    lcm=1
    #print(p_lis)
    for key in p_lis:
        lcm=(lcm*pow(key,p_lis[key],mod))%mod
    ans=0
    #print(lcm)
    for a in A:
        b=lcm*pow(a,mod-2,mod)%mod
        ans=(ans+b)%mod
    print(ans)


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

import queue
N, M = map(int, input().split())
G = [[] for _ in range(N)]

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

def dfs(Graph, N, start):
    q = queue.Queue()
    dist = [-1] * N
    dist[start] = 0
    q.put(start)

    while not q.empty():
        v = q.get()
        for u in G[v]:
            if dist[u] != -1:
                continue
            dist[u] = dist[v] + 1
            q.put(u)

    return dist
if dfs(G, N, 0)[-1] > 2 or dfs(G, N, 0)[-1] == -1:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

### FIXED CODE ###

import queue
N, M = map(int, input().split())
G = [[] for _ in range(N)]

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

def dfs(Graph, N, start):
    q = queue.Queue()
    dist = [-1] * N
    dist[start] = 0
    q.put(start)

    while not q.empty():
        v = q.get()
        if dist[v] >1:
            continue
        for u in G[v]:
            if dist[u] != -1:
                continue
            dist[u] = dist[v] + 1
            q.put(u)

    return dist
if dfs(G, N, 0)[-1] > 2 or dfs(G, N, 0)[-1] == -1:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')
### BUGGY CODE ###

LI = lambda: list(map(int, input().split()))

N, K = LI()
H = LI()

INF = 10 ** 15


def main():
    h = [0] + H
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(1, N + 1):
        for j in range(1, i + 1):
            v = INF
            for k in range(i):
                x = max(0, h[i] - h[k])
                v = min(v, dp[k][j - 1] + x)
            dp[i][j] = v

    ans = min([dp[i][N - K] for i in range(N - K, N + 1)])
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

LI = lambda: list(map(int, input().split()))

N, K = LI()
H = LI()

INF = 10 ** 15


def main():
    h = [0] + H
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(1, N + 1):
        for j in range(1, i + 1):
            v = INF
            for k in range(i):
                x = max(0, h[i] - h[k])
                v = min(v, dp[k][j - 1] + x)
            dp[i][j] = v

    ans = min([dp[i][N - K] for i in range(N - K, N + 1)])
    print(ans)


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

n = int(input())
num = [int(input()) for i in range(n)]

gra = [1]*n

for i in range(1,n):
    Max = 1
    for j in range(i):
        if num[j]<num[i] and gra[j]>=Max:
            Max = gra[j]
            gra[i] = Max+1

print(max(gra))

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import bisect
#D2
n = int(input())
a = [int(input()) for j in range(n)]
 
dp = [a[0]]
for i in range(1,n):
    if dp[-1] < a[i]:
        dp.append(a[i])
        #print(0,dp)
 
    else:
        dp[bisect.bisect_left(dp, a[i])] = a[i]
        #print(1,bisect.bisect_left(dp, a[i]),dp)
print(len(dp))