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

import sys


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return


# B
def B():
    s = S()
    for i in range(len(s)):
        if i % 2:
            if s[i] not in ["L", "U", "D"]:
                print("No")
                return
        else:
            if s[i] not in ["R", "U", "D"]:
                print("No")
                return
    print("Yes")
    return


# C
def C():
    n, k, q = LI()
    a = IR(q)
    sc = [0] * n
    for i in a:
        sc[i - 1] += 1
    for i in sc:
        print("Yes" if i > q - k else "No")
    return


# D
def D():
    n,m=LI()
    a=LI()
    for i in range(m):
        index = a.index(max(a))
        if a[index] > 0:
            a[index] = a[index]>>1
        else:
            break
    print(sum(a))
    return


# E
def E():
    return


# F
def F():
    return


# Unittest
def resolve():
    D()
    return


# Solve
if __name__ == "__main__":
    D()


### FIXED CODE ###

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return


# B
def B():
    s = S()
    for i in range(len(s)):
        if i % 2:
            if s[i] not in ["L", "U", "D"]:
                print("No")
                return
        else:
            if s[i] not in ["R", "U", "D"]:
                print("No")
                return
    print("Yes")
    return


# C
def C():
    n, k, q = LI()
    a = IR(q)
    sc = [0] * n
    for i in a:
        sc[i - 1] += 1
    for i in sc:
        print("Yes" if i > q - k else "No")
    return


# D
def D():
    n, m = LI()
    a = LI()
    q = []
    for i in range(n):
        heappush(q, -a[i])
    for i in range(m):
        x = heappop(q)
        x *= -1
        x >>= 1
        heappush(q, -x)
    print(-sum(q))
    return


# E
def E():
    return


# F
def F():
    return


# Unittest
def resolve():
    D()
    return


# Solve
if __name__ == "__main__":
    D()
### BUGGY CODE ###

L, R = map(int, input().split())

l_max = min(L + 2018, R-1)
r_min = min(R - 2018, L+1)
ans = float("inf")
for l in range(L, l_max+1):
    for r in range(r_min, R+1):
        if l >= r:
            continue
        ans = min(ans, l*r%2019)
print(ans)


### FIXED CODE ###

L, R = map(int, input().split())

l_max = min(L + 2018, R-1)
r_min = max(R - 2018, L+1)
ans = float("inf")
for l in range(L, l_max+1):
    for r in range(r_min, R+1):
        if l >= r:
            continue
        ans = min(ans, l*r%2019)
print(ans)
### BUGGY CODE ###

n = int(input())

chokudai = 0
aoki = 0
ans = 0
for i in range(n):
	t, a = map(int,input().split())
	if i == 0:
		chokudai = t
		aoki = a
		continue
	tmpt, tmpa = t, a
	while tmpt < chokudai or tmpa < aoki:
		tmpt += t
		tmpa += a
	ans += (tmpt-chokudai) + (tmpa-aoki)
	chokudai = tmpt
	aoki = tmpa
print(chokudai + aoki)

### FIXED CODE ###

def ceil(a, b):
	return -(-a//b)

n = int(input())
chokudai, aoki = 0, 0
for i in range(n):
	t, a = map(int,input().split())
	if i == 0:
		chokudai, aoki = t, a
		continue
	bairitsu = max(ceil(chokudai, t), ceil(aoki, a))
	t *= bairitsu
	a *= bairitsu
	#print(t, a)
	chokudai, aoki = t, a
print(chokudai + aoki)
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def main():
    N = NI()
    # P = primes(N)
    # D = [1] * (N+1)
    # for p in P:
    #     for i in range(1, N//p + 100):
    #         d = p * i
    #         if d > N:
    #             break
    #
    #         tmp = 0
    #         while d % p == 0:
    #             tmp += 1
    #             d = d // p
    #         D[p*i] *= tmp + 1
    ans = 1
    for i in range(2, N+1):
        pf = prime_fact(i)
        tmp = 1
        for a, b in pf.items():
            tmp *= b+1
        ans += tmp * i

    def num_divisors_table(n):
        table = [0] * (n + 1)

        for i in range(1, n + 1):
            for j in range(i, n + 1, i):
                table[j] += 1

        return table
    D = num_divisors_table(N)
    ans = 0
    for i in range(1, N+1):
        ans += D[i] * i
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def main():
    N = NI()


    def num_divisors_table(n):
        table = [0] * (n + 1)

        for i in range(1, n + 1):
            for j in range(i, n + 1, i):
                table[j] += 1

        return table
    D = num_divisors_table(N)
    ans = 0
    for i in range(1, N+1):
        ans += D[i] * i
    print(ans)

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

import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx < end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.9 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
start = 0
K = L * int(N ** 0.3 + 2 )
if K > N : K = N
end = K
while (end <= N):
    ANS = SME(A, start, end, L, ANS)
    start = end
    end += K 
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import heapq

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

def heap_push(my_lst, a):
    heapq.heappush(my_lst, a)
    return my_lst


def dfs(k, lst, my_lst):
    if k == 0:
        return max(sum(my_lst), 0)
    
    if len(my_lst) == 0:
        a = dfs(k-1, lst[1:], heap_push(my_lst[:], lst[0]))
        b = dfs(k-1, lst[:-1], heap_push(my_lst[:], lst[-1]))
        return max(a, b)
                
    if len(lst) == 0:
        return dfs(k-1, lst + heapq.nsmallest(1,my_lst), my_lst[1:])
                
    else:
        a = dfs(k-1, lst[1:], heap_push(my_lst[:], lst[0]))
        b = dfs(k-1, lst[:-1], heap_push(my_lst[:], lst[-1]))
        
        c = dfs(k-1, lst + heapq.nsmallest(1,my_lst), my_lst[1:])
        d = dfs(k-1, heapq.nsmallest(1,my_lst) + lst, my_lst[1:])
        return max(a,b,c,d)
    
my_lst = []
heapq.heapify(my_lst)
print(dfs(k, lst, []))

### FIXED CODE ###

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

res = 0
max_num = min(n, k)
for i in range(max_num+1):
    for j in range(max_num+1 - i):
        my_lst = []
        my_lst += lst[:i]
        if j != 0:
            my_lst += lst[-j:]
        
        s = sum(my_lst)
        sorted_my_lst = sorted(my_lst)
        #print('my_lst :', my_lst)
        for l in range(k- i - j):
            if len(my_lst) > l:
                if sorted_my_lst[l] < 0:
                    s -= sorted_my_lst[l]
        res = max(res, s)

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

# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()
C = Counter(A)

# dp[i][j][k] := 3個残りがi個、2個残りがj個、1個残りがk個である状態にするまでの操作回数の期待値
dp = list3d(N+1, N+1, N+1, INF)
# 全て残0なら残り回数は0
dp[0][0][0] = 0
for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            if i == j == k == 0:
                continue
            # 今現在残っている皿を取る確率
            tmp = (i + j + k) / N
            # そのために必要な回数
            res = 1 / tmp
            # それ以降に必要な回数
            if i and j < N: 
                res += (i/N) / tmp * dp[i-1][j+1][k]
            if j and k < N: 
                res += (j/N) / tmp * dp[i][j-1][k+1]
            if k: 
                res += (k/N) / tmp * dp[i][j][k-1]
            dp[i][j][k] = res
print(dp[C[3]][C[2]][C[1]])


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()
C = Counter(A)

# dp[i][j][k] := 3個残りがi個、2個残りがj個、1個残りがk個である状態にするまでの操作回数の期待値
dp = list3d(N+1, N+1, N+1, INF)
# 全て残0なら残り回数は0
dp[0][0][0] = 0.0
for i in range(N+1):
    for j in range(N+1):
        # 枝刈り
        if i+j > N:
            break
        for k in range(N+1):
            # 枝刈り
            if i+j+k > N:
                break
            if i == j == k == 0:
                continue
            # 今現在残っている皿を取る確率
            tmp = (i + j + k) / N
            # そのために必要な回数
            res = 1 / tmp
            # それ以降に必要な回数
            if i and j < N: 
                res += (i/N) / tmp * dp[i-1][j+1][k]
            if j and k < N: 
                res += (j/N) / tmp * dp[i][j-1][k+1]
            if k: 
                res += (k/N) / tmp * dp[i][j][k-1]
            dp[i][j][k] = res
print(dp[C[3]][C[2]][C[1]])
### BUGGY CODE ###

def main():
    n=int(input())
    a=sorted(map(int,input().split()))
    cnt=0
    for i in range(n):
        c=a[i]
        for j in range(n):
            #print(f"c:{c} <> a:{a[j]}")
            if i == j:
                continue
            if 2*c < a[j]:
                break
            c += a[j]
        else:
            break
    return n-i
    
if __name__ == "__main__":
    print(main())

### FIXED CODE ###

import itertools
def main():
    n=int(input())
    a=sorted(map(int,input().split()))
    b=list(itertools.accumulate(a))
    cnt=0
    for i in reversed(range(1, n)):
        if b[i-1]*2 < a[i]:
            return n-i
    return n
            
if __name__ == "__main__":
    print(main())
### BUGGY CODE ###

import itertools
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

L = list(itertools.product(A,B,C,repeat=1))
cnt = 0
for i,j,k in L:
    if i<j<k:
        cnt += 1
print(cnt)

### FIXED CODE ###

import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()

ans = 0
for x in B:
    # 小さい
    sm = bisect.bisect_left(A,x)
    # 大きい
    bi = len(C) - bisect.bisect_right(C,x)
    ans += sm*bi
print(ans)
### BUGGY CODE ###

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

u = UnionFind(n)
for i in range(m):
    x = xy[i][0]
    y = xy[i][1]
    u.union(x, y)

idx_dict = dict()
keys = []
for i in range(n):
    idx = u.find(i + 1)
    if idx not in keys:
        idx_dict[idx] = [i]
        keys.append(idx)
    else:
        idx_dict[idx].append(i)

counter = 0
for k in keys:
    l = idx_dict[k]
    template = []
    for i in range(len(l)):
        template.append(p[l[i]] - 1)

    counter += len(set(l) & set(template))

print(counter)


### FIXED CODE ###

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

from collections import defaultdict
g = defaultdict(list)
for x, y in xy:
    x, y = x - 1, y - 1
    g[x].append(y)
    g[y].append(x)

visited = [0] * n
ans = 0

for i in range(n):
    if visited[i] == 0:
        q = [i]
        visited[i] = 1
        s = set([i])
        while q:
            cur = q.pop()
            for target in g[cur]:
                if visited[target] == 0:
                    visited[target] = 1
                    q.append(target)
                    s.add(target)

        ps = set()
        for j in s:
            ps.add(p[j] - 1)

        intersect = s & ps
        ans += len(list(intersect))
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
dic = {}
for i in range(m):
  a,b = map(int,input().split())
  if a not in dic:
    dic[a]=[b]    
  else:    
    if b not in dic[a]:
      dic[a].append(b)      
      
  if b not in dic:
    dic[b]=[a]
    if a not in dic[b]:
      dic[b].append(a)
      
islands = set()
for i in dic[1]:
  islands.add(i)
  for j in dic[i]:
    islands.add(j)
    
if n in islands:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')          

### FIXED CODE ###

n,m = map(int,input().split())
dic = {i+1:set() for i in range(n)}
for i in range(m):
  a,b = map(int,input().split())
  dic[a].add(b)
  dic[b].add(a)
        
ans = 'IMPOSSIBLE'
for i in dic[1]:   
  if n in dic[i]:
    ans = 'POSSIBLE'
    break
    
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
a = [num % MOD if num >= MOD else num for num in a]

ans = 0
for i in range(len(a)):
	for j in range(i + 1, len(a)):
		acc = a[i] * a[j]
		ans += acc % MOD if acc >= MOD else acc
		ans %= MOD
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
a = [num % MOD if num >= MOD else num for num in a]

sum_list = [0]
for i in range(n):
	sum_list.append((a[i] + sum_list[i]) % MOD)
# print(sum_list)

ans = 0
for i in range(len(a)):
	ans += a[i] * (sum_list[-1] - sum_list[i + 1])
	ans %= MOD

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

n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
d = [0]*m
for i in range(1,m):
    d[i] = x[i]-x[i-1]

for i in range(n-1):
    if d == []:
        break
    else:
        d.remove(max(d))
ans = 0
for i in range(len(d)):
    ans += d[i]
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
d = [0]*m
for i in range(1,m):
    d[i] = x[i]-x[i-1]
d.sort()
if n < m:
    d = d[1:m-n+1]
else:
    d = [0]
ans = 0
for i in range(len(d)):
    ans += d[i]
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

for i in range(n):
    ans = a.copy()
    del ans[i]
    print(max(ans))

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

comp = sorted(a, reverse = True)

Fmax = comp[0]
Smax = comp[1]

for i in range(n):
    if a[i] == Fmax:
        print(Smax)
    
    else:
        print(Fmax)
### BUGGY CODE ###

S=list(input())
T=list(input())
len0=len(S)
S=S*(len(T)//len0+1)

S=S+S

p=26
mod=(1<<31)+7# 互いに素なものを指定

TABLE=[0]# Rolling Hashのテーブル. 最初は0
LEN=len(S)

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)# テーブルを埋める

NOW=0
LEN2=len(T)

for i in range(LEN2):
    NOW=(p*NOW%mod+ord(T[i])-97)%mod

TH=NOW

def hash_ij(i,j): # [i,j)のハッシュ値を求める
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod

OK=[0]*LEN

for i in range(LEN2,LEN):
    if hash_ij(i-LEN2,i)==TH:
        OK[i-LEN2]=1

OK=OK[:len0]

ANS=0

ST=[-1]*len0

for i in range(len0):
    if OK[i]==1 and ST[i]==-1:

        j=i
        count=0

        while OK[j]==1:
            
            if ST[j]!=-1:
                count+=ST[j]
                break
            
            count+=1
            ST[j]=1
            j=(j+LEN2)%len0
            if j==i:
                print(-1)
                import sys
                sys.exit()

        ST[i]=count
        ANS=max(ANS,count)

print(ANS)


### FIXED CODE ###

S=list(input())
T=list(input())
len0=len(S)
S=S*(len(T)//len0+1)

S=S+S

p=26
mod=(1<<31)+7# 互いに素なものを指定

TABLE=[0]# Rolling Hashのテーブル. 最初は0
LEN=len(S)

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)# テーブルを埋める

NOW=0
LEN2=len(T)

for i in range(LEN2):
    NOW=(p*NOW%mod+ord(T[i])-97)%mod

TH=NOW

def hash_ij(i,j): # [i,j)のハッシュ値を求める
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod

OK=[0]*LEN

for i in range(LEN2,LEN):
    if hash_ij(i-LEN2,i)==TH:
        OK[i-LEN2]=1

OK=OK[:len0]

ANS=0

ST=[-1]*len0

for i in range(len0):
    if OK[i]==1 and ST[i]==-1:

        j=i
        count=0

        while OK[j]==1:
            
            if ST[j]!=-1:
                count+=ST[j]
                break
            
            count+=1
            ST[j]=1
            j=(j+LEN2)%len0
            if j==i:
                print(-1)
                import sys
                sys.exit()

        ST[i]=count
        ANS=max(ANS,count)

print(ANS)
### BUGGY CODE ###

import bisect

N=int(input())
A=[int(input()) for i in range(N)]
lst=[]
nowN=max(A)+1
i=0
while i<N:
    if nowN>=A[i]:
        nowN=A[i]
        lst.append([A[i]])
    else:
        lst2=[n[-1] for n in lst]
        if min(lst2)<A[i]:
            for n in range(len(lst2)):
                if lst2[n]<A[i]:
                    lst[n].append(A[i])
                    break
        else:
            lst.append([A[i]])
    i+=1
print(len(lst))


### FIXED CODE ###

import bisect
import collections

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=collections.deque([])
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if lst:
            lst.pop()
        else:
            count+=1
        continue
    idx=bisect.bisect_left(lst,A[i])-1
    #print(idx,lst,A[i])
    if idx<0:
        lst.appendleft(A[i])
        count+=1
    else:
        lst[idx]=A[i]

print(count)
### BUGGY CODE ###

A, B, N = map(int,input().split())
ans = -100000000000
pre = 10**9
ans = 0
for i in range(N+1):
    t = (A*i) // B - A * (i//B)
    if pre < ans :
        break
    if ans < t:
        ans = t
    pre = t
print(ans)

### FIXED CODE ###

import math
def f(x):
    return math.floor(A*x/B)

A, B, N = map(int, input().split())
print(f(min(B-1,N)))
### BUGGY CODE ###

# D - Sum of Divisors
N = int(input())
ans = 0

for i in range(1, N + 1):
	j = 1
	
	while True:
		if i * j <= N:
			#print(i * j)
			
			ans += i * j
			j += 1
		else:
			break

print(ans)
	

### FIXED CODE ###

# D - Sum of Divisors
N = int(input())
ans = (1 + N) * N

for i in range(2, N//2 + 1):
	j = 2
	
	while True:
		if i * j <= N:
			
			ans += i * j
			j += 1
		else:
			break

print(ans - 1)