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

N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
pq = [list(map(int, input().split())) for _ in range(Q)]

table = [[0 for _i in range(N+1)] for _j in range(N+1)]
accum = [[0 for _i in range(N+1)] for _j in range(N+1)]
ans = [[0 for _i in range(N+1)] for _j in range(N+1)]

for line in LR:
    table[line[0]][line[1]] += 1
for i in range(1, N+1):
    for j in range(i, N+1):
        accum[i][j] = accum[i][j-1] + table[i][j]
for i in range(1, N+1):
    for j in range(i, N+1):
        ans[i][j] = sum([accum[k][j] - accum[k][i-1] for k in range(i, j+1)])

for question in pq:
    p = question[0]
    q = question[1]
    print(ans[p][q])

### FIXED CODE ###

N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
pq = [list(map(int, input().split())) for _ in range(Q)]

table = [[0 for _i in range(N+1)] for _j in range(N+1)]
accum = [[0 for _i in range(N+1)] for _j in range(N+1)]
accum2 = [[0 for _i in range(N+1)] for _j in range(N+1)]

for line in LR:
    table[line[0]][line[1]] += 1
# よこ
for i in range(1, N+1):
    for j in range(1, N+1):
        accum[i][j] = accum[i][j-1] + table[i][j]
# 縦
for i in range(1, N+1):
    for j in range(1, N+1):
        accum2[i][j] = accum2[i-1][j] + accum[i][j]

# for i in range(1, N+1):
#     for j in range(i, N+1):
#         ans[i][j] = sum([accum[k][j] - accum[k][i-1] for k in range(i, j+1)])

for question in pq:
    p = question[0]
    q = question[1]
    print(accum2[q][q] - accum2[p-1][q] - accum2[q][p-1] + accum2[p-1][p-1])
### BUGGY CODE ###

a,b,k = map(int, input().split())
for i in range(k):
    if a >= 1:
        a -= 1
    elif b >= 1:
        b -= 1
print(str(a) + ' ' +str(b))

### FIXED CODE ###

a,b,k = map(int, input().split())
if a <= k:
    a, k = 0, k-a
    b -= k
else:
    a -= k
if b < 0:
    b = 0
print(str(a)+' '+str(b))
### BUGGY CODE ###

from functools import lru_cache


@lru_cache(maxsize=None)
def get_sum(k):
    filtered = map(lambda x: x[1]-1 if x[0]
                   == k else x[1], a_dict.items())
    filtered = map(lambda x: x*(x-1)//2, filtered)
    return sum(filtered)


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

a_dict = {}
for a in a_list:
    if not(a in a_dict):
        a_dict[a] = 0

    a_dict[a] += 1


for i in range(n):
    k = a_list[i]
    print(get_sum(k))


### FIXED CODE ###

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

a_dict = {}
for a in a_list:
    if not(a in a_dict):
        a_dict[a] = 0
    a_dict[a] += 1
    
ans = sum(map(lambda x: x*(x-1)//2, a_dict.values()))

for i in range(n):
    k = a_list[i]
    before = a_dict[k]*(a_dict[k]-1) // 2
    after = (a_dict[k]-1)*(a_dict[k]-2) // 2
    print(ans - (before - after))
### BUGGY CODE ###

n = int(input())
L = sorted(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 k in range(j + 1, n):
            c = L[k]
            if a < b + c:
                pass
            else:
                break
            if b < c + a:
                pass
            else:
                break
            if c < a + b:
                pass
            else:
                break
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
L = sorted(list(map(int, input().split())), reverse = True)

def judge(a:int, b:int, c:int):
    if a < b + c:
        pass
    else:
        return False
    if b < c + a:
        pass
    else:
        return False
    if c < a + b:
        pass
    else:
        return False
    return True

def binary_search(l:int, r:int):
    while r - l > 1:
        mid = (l + r) // 2
        c = L[mid]
        if judge(a, b, c) == True:
            l = mid
        else:
            r = mid
    return l

ans = 0
for i in range(n - 2):
    a = L[i]
    for j in range(i + 1, n - 1):
        b = L[j]
        f1 = judge(a, b, L[j + 1])
        f2 = judge(a, b, L[n - 1])
        if f1 == True:
            if f2 == False:
                ans += binary_search(j, n - 1) - j 
            else:
                ans += n - j - 1
        else:
            pass
    
print(ans)
### BUGGY CODE ###


a, b, k = map(int, input().split())
for i in range(a, b+1):
    if i-a+1 <= k or b-i+1 <= k:
        print(i)

### FIXED CODE ###


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

end = min(b, a+k-1)
for i in range(a, end+1):
    print(i)

start = max(b-k+1, a+k)
for i in range(start, b+1):
    print(i)
### BUGGY CODE ###

n, w = [int(e) for e in input().split()]
t = [-1 for i in range(w + 1)]
t[w] = 0
for _ in range(n):
  nw, nv = [int(e) for e in input().split()]
  for i in range(nw, w + 1):
    if t[i] == -1:
      continue
    if t[i - nw] < t[i] + nv:
      t[i - nw] = t[i] + nv
print(max(t))


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

R,C,K = map(int, input().split())

d = [[0 for _ in range(C+1)] for _ in range(R+1)]
dp = [[[0 for _ in range(4)] for _ in range(C+1)] for _ in range(R+1)]

for i in range(K):
    r, c, v = map(int, input().split())
    d[r-1][c-1] = v
for i in range(R):
    for j in range(C):
        # kが大きい方からやらないとダメ。01ナップサックと同じ考え方。書き換えられた値を見ないように。
        for k in range(2, -1, -1):
            # 拾う遷移。d[i][j]を取るかどうかという判定
            dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k] + d[i][j])
        for k in range(4):
            dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k])
            dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k])
ans = 0

for k in range(4):
    ans = max(ans, dp[R-1][C-1][k])
print(ans)    

### FIXED CODE ###

R,C,K = map(int, input().split())

d = [[0 for _ in range(C+1)] for _ in range(R+1)]
dp = [[[0 for _ in range(C+1)] for _ in range(R+1)] for _ in range(4)]

for i in range(K):
    r, c, v = map(int, input().split())
    d[r-1][c-1] = v
for i in range(R):
    for j in range(C):
        # kが大きい方からやらないとダメ。01ナップサックと同じ考え方。書き換えられた値を見ないように。
        for k in range(2, -1, -1):
            # 拾う遷移。d[i][j]を取るかどうかという判定
            dp[k+1][i][j] = max(dp[k+1][i][j], dp[k][i][j] + d[i][j])
        for k in range(4):
            dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j])
            dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j])
ans = 0

for k in range(4):
    ans = max(ans, dp[k][R-1][C-1])
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())
cnt = 0
cnt_1 = 0
for i in range(N) :
    for j in range(i+1,N) :
        for k in range(j+1,N) :
            cnt_1 += 1
            if ((S[i] == S[j]) or (S[i] == S[k]) or (S[j] == S[k])) or (k == 2*j-i) :
                cnt += 1
print(cnt_1 - cnt)

### FIXED CODE ###

N = int(input())
S = list(input())
r,g,b = 0,0,0
k = 0
buf = 0

for i in range(N) :
    if S[i] == 'R' :
        r += 1
    elif S[i] == 'G' :
        g += 1
    else :
        b += 1

for j in range(N) :
    for i in range(j) :
        k = 2 * j - i
        if k <= N-1 :
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k] :
                buf += 1

print(r*g*b - buf)
### BUGGY CODE ###

def chmin(a, b):
    '''a>bならbを代入して返すメソッド'''
    if a > b:
        a = b
        return a
    else:
        return a


def main():
    '''もらうDPとして実装'''
    N, K = list(map(int, input().split()))
    H = list(map(int, input().split()))
    # 最小なものにコストを書き換えたいので初期値は大きく取る
    dp = [1000000000] * N

    # 最初はコスト０
    dp[0] = 0
    for i in range(1, N):
        dp[i] = chmin(dp[i], dp[i - 1] + abs(H[i] - H[i - 1]))
        if i>1:
            for j in range(2, K+1):
                dp[i] = chmin(dp[i], dp[i - j] + abs(H[i] - H[i - j]))
    print(dp[i])

main()

### FIXED CODE ###

def test():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf')]*N
    dp[0] = 0
 
    for i in range(1, N):
        dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i-K, 0), i))
 
    print(dp[-1])
 
if __name__ == '__main__':
    test()
### BUGGY CODE ###

n = int(input())
li = list(map(int, input().split()))
res = 0
for i in range(0, len(li)-1):
    for j in range(i+1, len(li)):
        pair = (li[i]*li[j])
        res += pair
res %= (10**9 + 7)
print(res)

### FIXED CODE ###

n = int(input())
li = list(map(int, input().split()))
res = 0
sum1 = sum(li)
sum2 = 0
m = 10**9 + 7
for i in range(0, len(li)-1):
    sum2 += li[i]
    res = (res + li[i]*(sum1-sum2))%m
print(res)
### BUGGY CODE ###

mod = 10**9 + 7
n, a, b = map(int, input().split())
ans = pow(2, n, mod)-1

# a
x = 1
for i in range(n - a + 1, n + 1):
    x *= i
y = 1
for i in range(1, a + 1):
    y *= i

a_ans = x*pow(y, mod-2, mod)

x = 1
for i in range(n - b + 1, n + 1):
    x *= i
y = 1
for i in range(1, b + 1):
    y *= i
b_ans = x*pow(y, mod-2, mod)
print((ans - a_ans - b_ans) % mod)


### FIXED CODE ###

mod = 10**9 + 7
n, a, b = map(int, input().split())
ans = pow(2, n, mod)-1


def nck(n, k, mod):
    bunbo = bunshi = 1
    for i in range(k):
        bunshi = (bunshi * (n-i)) % mod
        bunbo = (bunbo * (i+1)) % mod
    return (bunshi * pow(bunbo, mod-2, mod)) % mod


print((ans - nck(n, a, mod) - nck(n, b, mod)) % mod)
### BUGGY CODE ###

import collections
s = input()
mod = 2019
mod_lst = [0]
tmp = 0
t = 1
for i in reversed(s):
    x = int(i) * t
    y = (x % mod + tmp) % mod
    mod_lst.append(y)
    tmp = y
    t = t*10

lst_count = collections.Counter(mod_lst)
count = 0
for j in lst_count.values():
    a = j*(j-1)//2
    count += a
print(count)

### FIXED CODE ###

s = input()
mod = 2019
mod_lst = [0]*mod
mod_lst[0] =1
x = 0
t = 1
for i in reversed(s):
    x += int(i) * t
    y = x % mod
    t *= 10
    t %= mod
    mod_lst[y] += 1


count = 0
for j in mod_lst:
    a = j*(j-1)//2
    count += a
print(count)
### BUGGY CODE ###

import math
from functools import reduce
a = int(input())
result = 0
# target_list = []
for x in range(1, a+1):
    for y in range(1, a+1):
        for z in range(1, a+1):
            result += reduce(math.gcd, (x, y, z))
            # target_list.append((x, y, z))

# for target in target_list:
    # result += reduce(math.gcd, target)
print(result)

### FIXED CODE ###

import math
from functools import reduce
a = int(input())
result = 0
for x in range(1, a+1):
    for y in range(1, a+1):
        for z in range(1, a+1):
            result += reduce(math.gcd, (x, y, z))
            
print(result)
### BUGGY CODE ###

a,b,n = map(int,input().split())
c = 0
for i in range(n+1):
    ans = int(a*i/b)-a*int(i/b)
    if ans > c:
        c = ans
print(c)

### FIXED CODE ###

a,b,n = map(int,input().split())
c = 0
if n >=b:
    i = b-1
else:
    i =n
ans = int(a*i/b)-a*int(i/b)
print(ans)
### BUGGY CODE ###

Q=int(input())
for i in range(Q):
    A,B=map(int,input().split())
    if A>B:
        A,B=B,A
    M=A*B-1
    CNT=B
    cnt=0
    for i in range(A,B):
        if CNT<=A:
            break
        if A<M//i<CNT:
            cnt+=1
            CNT=M//i
        elif M//i>=CNT and CNT-1>A:
            cnt+=1
            CNT-=1
        else:
            break
    print(cnt+(A-1)*2)

### FIXED CODE ###

Q=int(input())
for i in range(Q):
    A,B=map(int,input().split())
    if A>B:
        A,B=B,A
    if A==B:
        print((A-1)*2)
    elif A+1==B:
        print((A-1)*2)
    else:
        SQ=int(pow(A*B,0.5))
        if SQ**2==A*B:
            print((SQ-1)*2-1)
        elif SQ*(SQ+1)<A*B:
            print((SQ-1)*2+1)
        else:
            print((SQ-1)*2)
### BUGGY CODE ###

def go(s,b):
    count=-1
    for i in b:
        if s>=i:
           count+=1

    return count

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

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

c,d=[],[]
s=0
for i in a:
   s+=i
   c.append(s)
s=0
for i in b:
   s+=i
   d.append(s)

mx=0
for i,j in enumerate(c):
    if j<=k:
        for q,w in enumerate(d):
            if j+w<=k:
                if i+q+2>mx:
                    mx=i+q+2
        if i+1>mx:
            mx=i+1
for q,w in enumerate(d):
    if w<=k:
        if q+1>mx:
            mx=1+q
print(mx)


### FIXED CODE ###

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

a = [0]+list(map(int, input().split(" ")))
b = [0]+list(map(int, input().split(" ")))

for i in range(1, n+1):
    a[i] += a[i - 1]
for i in range(1, m+1):
    b[i] += b[i - 1]

j,mx= m,0
for i in range(n+1):
    if a[i]>k:
        break
    while(b[j]>k-a[i]):
        j-=1
    if (i+j>mx):
        mx=i+j
print(mx)
### BUGGY CODE ###

import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nms = lambda: map(str, sys.stdin.readline().split())
nl = lambda: list(nm())

n, k = nm()
h = nl()
h.insert(0, h[0])
INF = 10 ** 9
dp = [INF for _ in range(n + 1)]
dp[1] = 0

for i in range(2, n + 1):
    x = max(i - k, 1)
    dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(x, i)])
print(dp[-1])


### FIXED CODE ###

import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nms = lambda: map(str, sys.stdin.readline().split())
nl = lambda: list(nm())

n, k = nm()
h = nl()
h.insert(0, h[0])
INF = 10 ** 9
dp = [INF for _ in range(n + 1)]
dp[1] = 0

for i in range(2, n + 1):
    x = max(i - k, 1)
    dp[i] = min([d + abs(h[i] - hd) for d, hd in zip(dp[x:i], h[x:i])])
print(dp[-1])
### BUGGY CODE ###

from collections import Counter 
import itertools

N = int(input())
D = list(map(int, input().split()))
M = Counter(D)
if max(M.values()) > 2:
    print(0)
elif 0 in D:
    print(0)
else:
    D = [[x, 24-x] for x in D]
    generator = list(itertools.product([0, 1], repeat=N))
    D_gen = [[D[i][g[i]] for i in range(N)] for g in generator]
    ans = 0
    for d in D_gen:
        tmp = [0] + sorted(d) + [24]
        s = 13
        for i in range(N+1):
            s = min(s, tmp[i+1]-tmp[i])
        ans = max(ans, s)
    print(ans)


### FIXED CODE ###

from collections import Counter 
import itertools

N = int(input())
D = list(map(int, input().split()))
D.append(12)
M = Counter(D)
if max(M.values()) > 2:
    print(0)
elif 0 in D:
    print(0)
elif N > 11:
    print(1)
else:
    D.remove(12)
    D = [[x, 24-x] for x in D]
    generator = list(itertools.product([0, 1], repeat=N))
    D_gen = [[D[i][g[i]] for i in range(N)] for g in generator]
    ans = 0
    for d in D_gen:
        if len(set(d)) < N:
            pass
        else:
            tmp = [0] + sorted(d) + [24]
            s = 13
            for i in range(N+1):
                s = min(s, tmp[i+1]-tmp[i])
            ans = max(ans, s)
    print(ans)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
N,M = map(int,input().split())
A = list(map(int,input().split()))
heapify(A)
for i in range(M):
    B,C = map(int,input().split())
    for k in range(B):
        heappush(A,C)
        a = heappop(A)
        if a>=C:break
print(sum(A))

### FIXED CODE ###

import bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))
D = []
for _ in range(M):
  D.append(list(map(int,input().split())))
D.sort(key=lambda x:x[1], reverse=True)
cnt = 0
ans = []
for d in D:
  b,c = d[0],d[1]
  ans += [c for _ in range(b)]
  cnt += b
  if cnt>=N:
    break
ans = ans[:min(cnt,N)] + A
ans.sort(reverse=True)
print(sum(ans[:N]))
### BUGGY CODE ###

from collections import defaultdict
import sys


def input(): return sys.stdin.readline().rstrip()


r, c, K = map(int, input().split())

dp = [[[0]*(c+1) for _ in range(r+1)] for i in range(4)]

# dp[N][i][j] := (i,j) にN個目でたどりつく方法
d = {(i, j): 0 for i in range(r+1) for j in range(c+1)}

for _ in range(K):
    r_, c_, v = map(int, input().split())
    d[(r_, c_)] += v
for i in range(1, r+1):
    for j in range(1, c+1):
        v = d[(i, j)]
        if v > 0:
            maxi = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(maxi, dp[0][i][j-1])
            dp[1][i][j] = max(dp[1][i][j-1], dp[0][i][j-1]+v, maxi+v)
            dp[2][i][j] = max(dp[2][i][j-1], dp[1][i][j-1]+v)
            dp[3][i][j] = max(dp[3][i][j-1], dp[2][i][j-1]+v)

        elif v == 0:
            maxi = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], maxi)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]


ans = max(dp[k][r][c] for k in range(4))

print(ans)

### FIXED CODE ###

from collections import defaultdict
import sys


def input(): return sys.stdin.readline().rstrip()


r, c, K = map(int, input().split())

dp = [[[0]*(c+1) for _ in range(r+1)] for i in range(4)]

# dp[N][i][j] := (i,j) にN個目でたどりつく方法
d = [[0 for i in range(c+1)] for j in range(r+1)]

for _ in range(K):
    r_, c_, v = map(int, input().split())
    d[r_][c_] = v
for i in range(1, r+1):
    for j in range(1, c+1):
        v = d[i][j]
        if v > 0:
            maxi = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(maxi, dp[0][i][j-1])
            dp[1][i][j] = max(dp[1][i][j-1], dp[0][i][j-1]+v, maxi+v)
            dp[2][i][j] = max(dp[2][i][j-1], dp[1][i][j-1]+v)
            dp[3][i][j] = max(dp[3][i][j-1], dp[2][i][j-1]+v)

        elif v == 0:
            maxi = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], maxi)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]


ans = max(dp[k][r][c] for k in range(4))

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

H, W, K = map(int, input().split())
S = [list(input()) for _ in range(H)]

ans = 10 ** 6

def calc(lst): #lst: 区切りを与える
    n = sum(lst) + 1 #n+1個に縦を区切る
    tmp = [0] * n
    count = n - 1 #区切る本数
    for w in range(W):
        position = 0
        now = [0] * n
        for h in range(H):
            if S[h][w] == '1': #ホワイトチョコレートのとき
                now[position] += 1
            if lst[h] == 1:
                position += 1
        
        flag = True
        for i in range(n):
            if tmp[i] + now[i] > K:
                flag = False

        if flag:
            for i in range(n):
                tmp[i] += now[i]
        else:
            count += 1
            for i in range(n):
                tmp[i] = now[i]
    for i in range(n):
        if now[i] > K:
            count += 10 ** 6
            
    return count

for i in range(2 ** (H - 1)):
    lst = [0] * (H)
    for j in range(H - 1):
        if (i >> j) & 1:
            lst[j] = 1
    ans = min(calc(lst), ans)

print (ans)
        

### FIXED CODE ###

H, W, K = map(int, input().split())
S = [list(input()) for _ in range(H)]

ans = 10 ** 6

def calc(lst): #lst: 区切りを与える
    n = sum(lst) + 1 #n+1個に縦を区切る
    tmp = [0] * n
    count = n - 1 #区切る本数
    for w in range(W):
        position = 0
        now = [0] * n
        for h in range(H):
            if S[h][w] == '1': #ホワイトチョコレートのとき
                now[position] += 1
            if lst[h] == 1:
                position += 1
        
        flag = True
        for i in range(n):
            if tmp[i] + now[i] > K:
                flag = False

        if flag:
            for i in range(n):
                tmp[i] += now[i]
        else:
            count += 1
            for i in range(n):
                tmp[i] = now[i]
    for i in range(n):
        if now[i] > K:
            count += 10 ** 6
            
    return count

for i in range(2 ** (H - 1)):
    lst = [0] * (H)
    for j in range(H - 1):
        if (i >> j) & 1:
            lst[j] = 1
    ans = min(calc(lst), ans)

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

N = int(input())
lis = list(map(int,input().split()))
ans = 1
for i in range(N):
  ans = ans*lis[i]
if ans > 1000000000000000000:
  print(-1)
else:
  print(ans)
  

### FIXED CODE ###

N = int(input())
lis = list(map(int,input().split()))
ans = 1
flag = True
if 0 in lis:
  print(0)
else:
  for i in range(N):
    ans = ans*lis[i]
    if ans > 1000000000000000000:
      print(-1)
      flag = False
      break
  if flag == True:
    print(ans)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
y = sorted(x)
for i in range(n):
  if y.index(x[i]) < n//2:
    print(y[n//2])
  else:
    print(y[n//2-1])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
y = sorted(x)
a = y[n//2-1]
b = y[n//2]
for i in range(n):
  print(a if x[i] > a else b)
### BUGGY CODE ###

monster, hisatu = map(int, input().split())
m_life = list(map(int, input().split()))
count = 0
if hisatu >= len(m_life):
    print(0)
else:
    for i in range(hisatu):
        m_life.remove(max(m_life))
    for i in m_life:
        count += i
    print(count)

### FIXED CODE ###

monster, hisatu = map(int, input().split())
m_life = list(map(int, input().split()))
m_life.sort()
count = 0
for i in range(len(m_life)-hisatu):
    count += m_life[i]
print(count)
### BUGGY CODE ###

n = int(input())
p_list = map(int, input().split())
left_list = []
res = 0
for i in p_list:
  if i == 1:
    res += 1
  else:
    filter_left = list(filter(lambda x: i > x, left_list))
    if len(filter_left) == 0:
      res += 1
  left_list.append(i)
print(res)

### FIXED CODE ###

n = int(input())
p_arr = list(map(int, input().split()))
min_i = 9999999999999999999999999
res = 0
for i in p_arr:
  if i == 1:
    res += 1
    break
  else:
    if i < min_i:
      res += 1
      min_i = i
print(res)
### BUGGY CODE ###

import re
def count_ac(s):
    p = re.compile('AC')
    return len(p.findall(s))

N, Q = input().split(' ')
s = input()

for i in range(int(Q)):
  a,b = map(int,input().split(' '))
  #print(s[a-1:b])
  if b-a <=1 :
    print(0)
  else :
    print(count_ac(s[a-1:b]))#, s[a-1:b])

### FIXED CODE ###

N, Q = input().split(' ')
s = input()

f = [0]
for i in range(1,int(N)):
  if (s[i-1]== 'A')&(s[i] == 'C'):
    f.append(f[i-1]+1)
  else :
    f.append(f[i-1])
  
for i in range(int(Q)):
  a,b = map(int,input().split(' '))
  print(f[b-1]-f[a-1])
### BUGGY CODE ###

N , M = [int(i) for i in input().split()]
data = list()
for i in range(M):
    data.append([int(i) for i in input().split()])
sorted_data = sorted(data, key=lambda x:x[1])

def num2str(num, len_str=6):
    return "0" * (len_str - len(str(num))) + str(num)

for i in range(M):
    rank = [j[1] for j in sorted_data if j[0] == data[i][0]].index(data[i][1])
    print(num2str(data[i][0]) + num2str(rank+1))

### FIXED CODE ###

N, M = [int(i) for i in input().split()]
data = list()
for i in range(M):
    p, y = [int(i) for i in input().split()]
    data.append([i, p, y])
data.sort(key=lambda x:(x[1],x[2]))
ind = 1
for j, (i, p, y) in enumerate(data):
    if data[j-1][1] != p:
        ind = 1
    data[j].append(ind)
    ind += 1
data.sort(key=lambda x:x[0])
for i, p, y, j in data:
    print(str(p).zfill(6) + str(j).zfill(6))
### BUGGY CODE ###

import sys

def solve():
    A = list(map(int, sys.stdin.readlines()))
    n = A[0]
    A[0] = -1
    L = [0] * (n + 1)
    for i, a_i in enumerate(A[1:], start=1):
        k = 0
        for j, a_j in enumerate(A[:i]):
            if a_j < a_i and L[j] > L[k]:
                k = j
        L[i] = L[k] + 1
    print(max(L))

solve()

### FIXED CODE ###

import sys
from bisect import bisect_left

def solve():
    A = map(int, sys.stdin)
    n = next(A)
    L = [next(A)]
    for a_i in A:
        if a_i > L[-1]:
            L.append(a_i)
        else:
            j = bisect_left(L, a_i)
            L[j] = a_i
    print(len(L))

solve()