Anton has the integer x. He is interested what positive integer, which doesn't exceed x, has the maximum sum of digits.

Your task is to help Anton and to find the integer that interests him. If there are several such integers, determine the biggest of them. 


-----Input-----

The first line contains the positive integer x (1 ≤ x ≤ 10^18) — the integer which Anton has. 


-----Output-----

Print the positive integer which doesn't exceed x and has the maximum sum of digits. If there are several such integers, print the biggest of them. Printed integer must not contain leading zeros.


-----Examples-----
Input
100

Output
99

Input
48

Output
48

Input
521

Output
499

Difficulty: interview

Starter code:

Solutions:
num = list(map(int, input()))
best = num[:]
for i in range(-1, -len(num) - 1, -1):
    if num[i] == 0:
        continue
    num[i] -= 1
    for j in range(i + 1, 0):
        num[j] = 9
    if sum(num) > sum(best):
        best = num[:]
s = ''.join(map(str, best)).lstrip('0')
print(s)


s_num = input()
num = int(s_num)
digs = [int(s_num[i]) for i in range(len(s_num))]

max_sum = sum(digs)
res = num
for i in range(len(s_num)):
    if (digs[i] != 0):
        digs[i] -= 1
        n_sum = sum(digs[:i + 1]) + 9 * (len(s_num) - i - 1)
        if n_sum >= max_sum:
            n_res = int(''.join([str(digs[i]) for i in range(i + 1)]) + '9' * (len(s_num) - i - 1))
            if (n_sum == max_sum):
                res = max(n_res, res)
            else:
                res = n_res
            max_sum = n_sum

        digs[i] += 1
print(res)


a=int(input())
if(a//10==0):
    print(a)
    return
k=9
while(k<a):
    k=k*10+9
if(k==a):
    print(k)
else:
    k//=10
    k=int(str(a)[0]+str(k))
    i=len(str(k))-1
    z=k
    while(z>a):
        z=int(str(k)[0:i]+str(int(str(k)[i])-1)+str(k)[i+1:len(str(k))])
        i-=1
    print(z)    

x = int(input())
if x < 10:
    print(x)
elif x == int(str(x)[0] + '9'*(len(str(x))-1)):
    print(x)
else:
    a = str(x)[0] + '9' * (len(str(x)) - 1)
    a = list(a)
    for i in range(len(a) - 1, -1, -1):
        k = a[i]
        a[i] = str(int(a[i]) - 1)
        if x >= int(''.join(a)):
            print(int(''.join(a)))
            break
        a[i] = k


def sum_str(y):
    return sum(map(int, str(y)))


x = input()
length = len(x)
bad_answer = str(int(x[0]) - 1) + '9' * (length - 1) 
total = sum_str(bad_answer)


if length == 1 or sum_str(x) >= total:
    print(x)
else:
    for i in range(length - 1, 0, -1):
        new_total = 9 * (length - i)
        new_answer = str(int(x[:i]) - 1)
        new_total += sum_str(new_answer)

        if new_total >= total:
            new_answer = new_answer if new_answer != '0' else ''
            print(new_answer + '9' * (length - i))
            break
    else:
        print(bad_answer)


import sys

def calc(s):
    res =0
    for c in s:
        res+= int(c)
    return res


s = list(sys.stdin.readline().rstrip())
best = "".join(s) 
count = calc(s)

i = len(s)-1
while i!=0:
    i-=1
    if s[i+1]!= '9':
        s[i+1] = '9'
        while s[i]=='0':
            s[i]='9'
            i-=1
        s[i] = chr(ord(s[i])-1)
        c = calc(s)
        if count < c:
            count = c
            best = "".join(s)

if best[0] == '0':
    best = best[1:]

print(best)

x = input()
n = len(x)
if n == 1:
    print(x)
    return
ans = ""
s = 0
ps = 0
pn = ""
for i in range(n):
    ts = ps + int(x[i]) - 1 + 9 * (n - i - 1)
    if ts >= s:
        ans = pn + str(int(x[i]) - 1) + "9" * (n - i - 1)
        s = ts
    ps += int(x[i])
    pn += x[i]
if ps >= s:
    ans = pn
print(int(ans))

n = int(input())

def f(numb):
    lst = [numb]
    cap = 10

    while numb // cap > 0:
        lst.append((numb // cap - 1) * cap + cap - 1)
        cap *= 10

    return lst

def g(numb):
    lst = []
    while numb != 0:
        lst.append(numb % 10)
        numb //= 10

    return lst


maximum = max([sum(g(i)) for i in f(n)])

maximum = [i for i in f(n) if maximum == sum(g(i))]

print(max(maximum))

""" Created by Shahen Kosyan on 3/11/17 """

def __starting_point():
    x = input()

    if int(x) < 10:
        print(x)
        return

    arr = [int(a) for a in list(x)]
    x_sum = sum(arr)

    i = len(arr) - 1
    answer = ''
    while i > 0:
        if arr[i] != 9 and arr[i] != 8:
            arr[i - 1] -= 1
            answer = '9' + answer
        else:
            change = False
            for j in range(i - 1, 0, -1):
                if arr[j] < 9:
                    change = True
                    break

            if arr[i] == 8 and change:
                answer = '9' + answer
                arr[i - 1] -= 1
            else:
                if not change:
                    answer = str(arr[i]) + answer
                else:
                    answer = '9' + answer

        if i == 1 and arr[0] != 0:
            answer = str(arr[0]) + answer
        i -= 1

    answer = [int(a) for a in list(answer)]
    if x_sum == sum(answer):
        print(x)
    else:
        answer = [str(a) for a in answer]
        print(''.join(answer))

__starting_point()

x=input()
l=len(x)
x=int(x)
s='9'*l
sx=str(x)
m=int(s)
c=0
while c!=1:
    if m>x:
        m=m-10**(l-1)
    else:
        c=1
sm=str(m)
mm=[] 
for i in range(len(sm)):
    mm.append(int(sm[i]))
xx=[] 
for i in range(l):
    xx.append(int(sx[i]))
if m==x:
    print(m)
elif sum(xx)==sum(mm):
    print(x)
else:
    k=len(xx)-1
    while k>=0:
        if sum(xx)<sum(mm):
            if xx[k]==9:
                k-=1
            else:
                xx[k]=9
                xx[k-1]-=1
                k-=1
        else:
            if xx[0]==0:
                xx.remove(0)
            for b in range(len(xx)):
                xx[b]=str(xx[b])
            ww=''.join(xx)
            print(ww)
            break

x = input()
variants = [x] + [str(int(x[:i]) - 1) +
    '9' * (len(x) - i) for i in range(1, len(x))]
print(int(max(variants, key=lambda x: (sum(map(int, x)), int(x)))))


def sum_div(n):
    summa = 0
    while n > 0:
        summa = summa + n % 10
        n = n // 10
    return summa


def run(n):
    l_n = len(n)
    left = ''
    if l_n > 2 and '9' * l_n != n and n[1] == '9' and '9' * (l_n - 1) != n[1:]:
        left = n[0]
        n = n[1:]
        while l_n > 1 and n[1] == '9':
            left += n[1]
            n = n[1:]
            l_n = len(n)
    l_n = len(n)
    if len(n) == 1:
        return n
    elif '9' * (l_n - 1) == n[1:]:
        return left + n
    elif n[0] != '1':
        min_number = int(str(int(n[0]) - 1) + '9' * (l_n - 1))
        if sum_div(min_number) > sum_div(int(n)):
            return left + str(min_number)
        else:
            return left + n
    else:
        min_number = int('9' * (l_n - 1)) if l_n > 1 else 0
        if sum_div(min_number) > sum_div(int(n)):
            return left + str(min_number)
        else:
            return left + n


n = input()
print(run(n))


#This code is dedicated to Olya S.

def e(x):
    s=0
    while x>0:
        s+=x%10
        x//=10
    return s

def down(x):
    l=len(x)-1
    return str(int(x[0])-1)+'9'*l

n=input()
if len(n)>1 and n[1]=='9':
    print(n[0],end='')
    n=n[1:]
    while len(n)>1 and n[0]=='9' and n[1]=='9':
        print('9',end='')
        n=n[1:]

if e(int(n))>=e(int(down(n))):
    print(n)
else:
    print(int(down(n)))

        
     



        



def sum_n(n):
    l = len(n)

    summ = 0
    for i in range(l):
        summ += int(n[i])

    return summ

def transfer(x, i):
    x = list(x)
    
    x[i+1] = '9'
    if x[i] != '0':
        x[i] = str(int(x[i])-1)
    else:
        j = i
        while (j > 0) and (int(x[j]) == 0):
            x[j] = '9'
            j -= 1
        x[j] = str(int(x[j])-1)
    if (x[0] == '0'):
        del x[0]

    return x

x = list(input())
max_cifr = sum_n(x)
maxnum = x
res = ''

for i in range(len(x)-2, -1, -1):
    x = transfer(x, i)
    if(max_cifr < sum_n(x)):
        max_cifr = sum_n(x)
        maxnum = x

for i in range(len(maxnum)):
    res = res+maxnum[i]
    
print(res)


x = input()
sum = 0
for i in x:
    temp = int(i)
    sum += temp

xlen = len(x)
one = int(x[0])
try:
    two = int(x[1])
except:
    two = 0

if (two == 9):
    count = 1
    for i in range(1, xlen):
        z = int(x[i])
        if (z == 9):
            count = i
        else:
            break
    answ = x[0:count] + "8" + ("9" * (xlen - count - 1))
elif (one == 1):
    answ = '9' * (xlen - 1)
else:
    answ = str((one - 1)) + ("9" * (xlen-1))

answ = str(answ)
sumansw = 0
for i in answ:
    temp = int(i)
    sumansw += temp

if (sum >= sumansw):
    print(x)
else:
    print(answ)

def sum1(x):  # подсчёт суммы цифр числа x
    summa = 0
    for i in x:
        summa += int(i)
    return summa


x = input()
c = sum1(x)
result = int(x)
n = len(x) - 1
j = n
for i in range(0, n):
    if x[i] != '0':
        ni = int(x[i]) - 1  # уменьшаю i-ый разряд на 1
        xi = x[0:i] + str(ni) + '9' * j  # строю новое число
        j -= 1
        ci = sum1(xi)
        if c < ci:
            c = ci
            result = int(xi)
        elif c == ci and result < int(xi):
            result = int(xi)
    else:
        j -= 1
        continue
print(result)


def f(n, k):
    n = str(n)
    if n[k] == "0":
        return f(n, k - 1)
    a = []
    for i in n:
        a.append(int(i))
    n = a
    n[k] = int(n[k]) - 1
    n[k + 1::] = [9] * (len(n) - k - 1)
    return n
a = input()
n = len(a)
ans = [int(x) for x in a]
ms = sum(ans)
for i in range(0, n):
    ca = f(a, i)
    cs = sum(ca)
    if cs> ms:
        ans = ca
        ms = cs
    elif cs == ms:
        if int(''.join([str(_) for _ in ca])) > int(''.join([str(_) for _ in ans])):
            ans = ca
print(int(''.join([str(_) for _ in ans])))

n = int(input().strip())

s = []
while n > 0:
    s.append(n % 10)
    n //= 10
s = s[::-1]

n = len(s)
ans = 0
best = -1
for i in range(n):
    res = sum(s[:i + 1]) - 1 + 9 * (n - i - 1)
    if res >= ans:
        ans = res
        best = i

def get(s, pos):
    ans = 0
    for i in range(len(s)):
        if i > pos:
            ans = ans * 10 + 9
        else:
            ans = ans * 10 + s[i]
            if i == pos:
                ans -= 1
    return ans

if sum(s) >= ans:
    print(get(s, n))
else:
    print(get(s, best))



def main():

	def sum(x):
		res = 0

		while x > 0:
			res += x % 10
			x //= 10

		return res

	n = input()
	first = n[0]
	p = [1]

	for i in range(1, 20):
		p.append(p[-1] * 10)

	data = []	
	for i in range(len(n)):
		if i > 0 and n[i] == '0':
			continue
		temp = n[:i] + str(max(0, int(n[i]) - 1)) + "9"* (len(n) - i - 1)
		data.append((sum(int(temp)), int(temp)))

	data.append((sum(int(n)), int(n)))
	
	data.sort(reverse=True)

	print(data[0][1])

	return

def __starting_point():
	main()
__starting_point()

def cnt_sum(str_num):
	sum = 0
	for a in str_num:
		sum += ord(a) - ord('0')
	return sum

str_a = input().strip()
max_sum = cnt_sum(str_a)
ans = str_a
cnt_digit = len(str_a)

for i in range(cnt_digit - 1, -1, -1):
	if str_a[i] != '0':
		new_str = str_a[:i] + chr(ord(str_a[i]) - 1) + '9'*(cnt_digit - i - 1)
		cur_sum = cnt_sum(new_str)
		if cur_sum > max_sum:
			max_sum = cur_sum
			ans = new_str

print(int(ans))


def summaX(x):
    k=0
    for el in x:
        k+=int(el)
    return k
n=input();N=[];Z=[]
for el in n:
    N.append(el)
z=summaX(N)
Z=N.copy()
for i in range(1,len(N)):
    if int(N[i])!=9:
        N[i-1]=int(N[i-1])-1
        for j in range(i,len(n)):
            N[j]=9
if z>=summaX(N):
    for el in Z:
        print(el,end='')
else:
    if N[0]==0:
        N.pop(0)
    for el in N:
        print(el,end='')


n = int(input())

def sumd(n):
	j = n
	sumn = 0
	while j:
		sumn += j % 10
		j //= 10
	return sumn

j = n
strn = str(n)
l = len(strn)
sumn = sumd(n)

stra = [i for i in str(n)]
i = 1
while i < l and stra[i] == '9':
	i += 1
if (i != l):
	stra[i - 1] = str(int(stra[i - 1]) - 1)
	while i < l:
		stra[i] = '9'
		i += 1

ss = ''
for i in range(l):
	ss += stra[i]
if ss[0] == '0':
	ss = ss[1:]
sn = int(ss)

if sn < n and sumd(sn) <= sumn:
	ss = strn
	sn = n

print(ss)


from random import randint

def f(s):
    a = 0
    for i in s:
        a += int(i)
    return a

def solve(n):
    n1 = list(str(n))
    ans = 0
    maxx = 0
    for i in range(len(n1)):
        n2 = n1[:i] + [str(int(n1[i]) - 1)] + ['9' for j in range(len(n1) - i - 1)]
        if f(n2) >= maxx:
            maxx = f(n2)
            ans = n2
    if f(n1) >= maxx:
        maxx = f(n1)
        ans = n1
    return [int(''.join(ans)), maxx]

def tl(n):
    ans = 0
    maxx = 0
    for i in range(1, n + 1):
        if f(list(str(i))) >= maxx:
            maxx = f(list(str(i)))
            ans = i
    return [ans, maxx]

'''for kkk in range(100):
    n = randint(1, 10 ** 5)
    c1 = solve(n)
    c2 = tl(n)
    if c1 != c2:
        print(n)
        print(c1)
        print(c2)
print('ok')'''
n = int(input())
print(solve(n)[0])


a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for length in range(2, 30):
    for first in range(1, 10):
        for pos in range(1, length):
            a.append(int(str(first) + '9' * (pos - 1) + '8' + '9' * (length - pos - 1)))
        a.append(int(str(first) + '9' * (length - 1)))
    
n = int(input())
l = 0
r = len(a)
while l < r - 1:
    middle = (l + r) // 2
    if (a[middle] <= n):
        l = middle
    else:
        r = middle
        
print(a[l])

def get(s):
    ans = 0
    for i in s:
        ans += (ord(i) - ord('0'))
    return ans


def solve1():
    x = input()
    n = len(x)
    best_ans = x
    best_val = get(x)
    ans = str('' if int(x[0]) - 1 == 0 else int(x[0]) - 1) + '9' * (n - 1)
    if get(ans) > best_val or (get(ans) >= best_val and int(ans) > int(best_ans)):
        best_ans = ans
        best_val = get(ans)
    for i in range(1, n):
        #print(ans)
        ans = x[:i] + str(int(x[i]) - 1) + '9' * (n - i - 1)
        if get(ans) > best_val or (get(ans) >= best_val and int(ans) > int(best_ans)):
            best_ans = ans
            best_val = get(ans)
    return best_ans
    
best = [0] * 10000
def solve2():
    nonlocal best
    was = 0
    for i in range(1, 10000):
        if get(str(i)) >= was:
            best[i] = i
            was = get(str(i))
        else:
            best[i] = best[i - 1]
    
def stress():
    solve2()
    for i in range(1, 10000):
        if int(solve1(str(i))) != best[i]:
            print(i, best[i], solve1(str(i)))

#stress()
print(solve1())