After passing a test, Vasya got himself a box of $n$ candies. He decided to eat an equal amount of candies each morning until there are no more candies. However, Petya also noticed the box and decided to get some candies for himself.

This means the process of eating candies is the following: in the beginning Vasya chooses a single integer $k$, same for all days. After that, in the morning he eats $k$ candies from the box (if there are less than $k$ candies in the box, he eats them all), then in the evening Petya eats $10\%$ of the candies remaining in the box. If there are still candies left in the box, the process repeats — next day Vasya eats $k$ candies again, and Petya — $10\%$ of the candies left in a box, and so on.

If the amount of candies in the box is not divisible by $10$, Petya rounds the amount he takes from the box down. For example, if there were $97$ candies in the box, Petya would eat only $9$ of them. In particular, if there are less than $10$ candies in a box, Petya won't eat any at all.

Your task is to find out the minimal amount of $k$ that can be chosen by Vasya so that he would eat at least half of the $n$ candies he initially got. Note that the number $k$ must be integer.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^{18}$) — the initial amount of candies in the box.


-----Output-----

Output a single integer — the minimal amount of $k$ that would allow Vasya to eat at least half of candies he got.


-----Example-----
Input
68

Output
3



-----Note-----

In the sample, the amount of candies, with $k=3$, would change in the following way (Vasya eats first):

$68 \to 65 \to 59 \to 56 \to 51 \to 48 \to 44 \to 41 \\ \to 37 \to 34 \to 31 \to 28 \to 26 \to 23 \to 21 \to 18 \to 17 \to 14 \\ \to 13 \to 10 \to 9 \to 6 \to 6 \to 3 \to 3 \to 0$.

In total, Vasya would eat $39$ candies, while Petya — $29$.

Difficulty: interview

Starter code:

Solutions:
def can(n, k):
    total = n
    s = 0

    while n > 0:
        cur = min(n, k)
        s += cur
        n -= cur

        n -= n // 10

    return s * 2 >= total

n = int(input())

le = 0
rg = n

while rg - le > 1:
    mid = (rg + le) // 2

    if can(n, mid):
        rg = mid
    else:
        le = mid

print(rg)


def consumed(n, k):
    res = 0
    while n:
        eaten = min(n, k)
        res += eaten
        n -= eaten
        n -= n // 10
    return res

n = int(input())

lo = 1
high = (n+1) // 2

while lo != high:
    mid = (lo + high) // 2
    if consumed(n, mid) * 2 >= n:
        high = mid
    else:
        lo = mid + 1

print(lo)


def read_input():
	return map(int, input().split())

n = int(input())

def eat(k, n):
	ans = 0
	while n >= k:
		ans += k
		n = max(0, (n - k) - (n - k) // 10)
	ans += n
	return ans

l = 1
r = n + 1

while r - l > 1:
	m = (l + r) >> 1
	if 2 * eat(m, n) >= n:
		r = m
	else:
		l = m

print(l if 2 * eat(l, n) >= n else l + 1)





def how_much_he_eats(n, k):
    result = 0
    while n != 0:
        eats = min([n, k])
        result += eats
        n -= eats
        n -= n // 10
    return result


n = int(input())

a, b, c = 1, n, 0

while a < b:
    c = (a + b) // 2

    if 2 * how_much_he_eats(n, c) >= n:
        b = c
    else:
        a = c + 1

print(a)


N = int(input())

def check(k):
    r = N
    a = 0
    while 1:
        if r < k:
            a += r
            break
        r -= k
        a += k
        r -= r//10
    return a*2 >= N


left = 0; right = 10**18+1
while left+1 < right:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)


n=int(input())
def query(k):
    t=n
    g=(n+1)//2
    while t:
        if t<k:
            g-=t
            break
        t-=k
        g-=k
        t=t-t//10
    if g<=0:return 1
    else:return 0

def bs(l,r):
    if l==r: return l
    m=(l+r)//2
    if query(m):return bs(l,m)
    else: return bs(m+1,r)

print(bs(1,1000000000000000000))


n = int(input())
l = 1
r = n
while l < r:
    m = (l + r) // 2
    cur = n
    k = m
    p = 0
    v = 0
    while cur:
        v += min(cur, k)
        cur -= min(cur, k)
        p += cur // 10
        cur -= cur // 10
    if v >= (n + 1) // 2:
        r = m
    else:
        l = m + 1
print(l)


def ii():
    return int(input())
def mi():
    return map(int, input().split())
def li():
    return list(mi())
    
def f(n, k):
    c = 0
    e = 0
    while n > 0:
        e += min(k, n)
        n -= k
        n -= n // 10
        c += 1
    return e

n = ii()
lo = 1
hi = th = (n + 1) // 2
while lo < hi:
    mid = (lo + hi) // 2
    cnt = f(n, mid)
    if cnt >= th:
        hi = mid
    else:
        lo = mid + 1
print(lo)

def f(n, k):
  m = n
  p, v = 0, 0
  while n > 0:
    p += min(k, n)
    n -= min(n, k)
    if p >= m // 2:
      break
    v += n // 10
    n -= n // 10
    if v > m // 2:
      break
  return p >= v

n = int(input())

l, u = 1, n
while (l != u):
  m = (l + u) // 2
  if not f(n, l) and not f(n, m):
    l = m + 1
  elif f(n, m) and f(n, u):
    u = m
print(l)


n = int(input())


def check(p):
    V = 0
    n_ = n
    while n_ > 0:
        temp = min(n_, p)
        V += temp
        n_ -= temp
        n_ -= n_ // 10

    return 2 * V >= n


def binSearch(a, b):
    left, right = a - 1, b + 1

    while right - left > 1:
        mid = (left + right) // 2

        if check(mid):
            right = mid

        else:
            left = mid

    return right


print(binSearch(1, n // 2))


n = int(input())


def eat(n, k):
    first = 0
    old = n
    while n > 0:
        if n > k:
            n -= k
            first += k
        else:
            first += n
            n = 0
        n -= n // 10
    if 2 * first >= old:
        return True
    return False


r = n + 1
l = 1


while l + 1 < r:
    m = l + (r - l - 1) // 2
    if eat(n, m):
        r = m + 1
    else:
        l = m + 1

print(l)


n = int(input())

half = (n-1) // 2 + 1

def simulate(k):
    remain = n
    vasya = 0
    
    while remain > 0:
        vasya += min(k, remain)
        remain -= k
        remain -= remain // 10
        
    return vasya >= half

hi = n
lo = 0

while hi - lo > 1:
    mid = (hi + lo) // 2
    
    if simulate(mid):
        hi = mid
    else:
        lo = mid

print(hi)

import math
n = int( input() )

def eat( k ):
    vasya = petya = 0
    candy = n
    while candy > 0:
        ate = 0
        ate = min( candy, k )
        vasya += ate
        candy -= ate
        if candy > 9:
            ate = candy // 10
            petya += ate
            candy -= ate
    return vasya >= petya

l = int( math.log( n, 2 ) )
a = 0
while l >= 0:
    b = 1 << l
    c = n - a - b
    if c > 0 and eat( c ):
        a += b
    l -= 1

print( n - a )


n = int(input())

if n <= 10:
	print("1")
	return

def check(k):
	out = 0
	cur = n
	while cur != 0:
		tmp = min(cur, k)
		cur -= tmp
		out += tmp
		if cur >= 10:
			cur -= cur // 10
	return out

l = 0
r = 10 ** 18 + 1
k = (l + r) // 2
while r - l > 1:
	if 2 * check(k) >= n:
		r = k
	else:
		l = k
	k = (l + r) // 2

print(k + 1)


n = int(input())

def check(k):
    a, b = 0, 0
    i = n
    while i > 0:
        t = min(k, i)
        a += t
        i -= t

        t = i // 10
        b += t
        i -= t
    # dbvar(k, a, b)
    return a >= b

left = 1
right = n
while right - left > 1:
    m = (left + right) // 2
    if check(m):
        right = m
    else:
        left = m
print(left if check(left) else right)

# 
#      ___           ___                       ___       ___           ___       ___     
#     /\__\         /\  \          ___        /\__\     /\  \         /\__\     /\  \    
#    /:/  /        /::\  \        /\  \      /:/  /    /::\  \       /:/  /    /::\  \   
#   /:/__/        /:/\:\  \       \:\  \    /:/  /    /:/\:\  \     /:/  /    /:/\ \  \  
#  /::\__\____   /::\ˉ\:\  \      /::\__\  /:/  /    /:/  \:\__\   /:/  /    _\:\ˉ\ \  \ 
# /:/\:::::\__\ /:/\:\ \:\__\  __/:/\/__/ /:/__/    /:/__/ \:|__| /:/__/    /\ \:\ \ \__\
# \/_|:|ˉˉ|ˉ    \/__\:\/:/  / /\/:/  /    \:\  \    \:\  \ /:/  / \:\  \    \:\ \:\ \/__/
#    |:|  |          \::/  /  \::/__/      \:\  \    \:\  /:/  /   \:\  \    \:\ \:\__\  
#    |:|  |          /:/  /    \:\__\       \:\  \    \:\/:/  /     \:\  \    \:\/:/  /  
#    |:|  |         /:/  /      \/__/        \:\__\    \::/__/       \:\__\    \::/  /   
#     \|__|         \/__/                     \/__/     ˉˉ            \/__/     \/__/    
#

n = int(input())

def che(k):
    nn = n
    cnt = 0
    while nn:
        if nn <= k:
            cnt += nn
            break
        cnt += k
        nn -= k
        nn -= nn//10
    return (cnt<<1) >= n

l, r = 1, 1000000000000000000
while l < r:
    mid = (l+r)>>1
    if (che(mid)):
        r = mid
    else:
        l = mid+1
print(r)



import sys
import math
import os.path
import random
from copy import deepcopy
from functools import reduce
from collections import Counter, ChainMap, defaultdict
from itertools import cycle, chain
from queue import Queue, PriorityQueue
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, nlargest, nsmallest
import bisect
from statistics import mean, mode, median, median_low, median_high
# CONFIG
sys.setrecursionlimit(1000000000)
# LOG 
def log(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
# INPUT
def ni():
    return map(int, input().split())
def nio(offset):
    return map(lambda x: int(x) + offset, input().split())
def nia():
    return list(map(int, input().split()))
# CONVERT
def toString(aList, sep=" "):
    return sep.join(str(x) for x in aList)
def toMapInvertIndex(aList):
    return {k: v for v, k in enumerate(aList)}
# SORT
def sortId(arr):
    return sorted(range(arr), key=lambda k: arr[k])
# MATH
def gcd(a,b):
    while b:
        a, b = b, a % b
    return a
# MAIN

n, = ni()

def check(k):
    v = 0
    p = 0
    x = n
    # log("check",k)
    while (x > 0):
        if (x > k):
            v += k
            x -= k
            if (x > 9):
                pd = x // 10
                p += pd
                x -= pd
        else:
            v += x
            x = 0
        
        # log(" ", x, v, p)
    
    # log(k,v,p)
    return v >= p

def bsearch(low, high):
    # log(low,high)
    if (low >= high):
        return low
    mid = (low + high) // 2
    if check(mid):
        return bsearch(low, mid)
    else:
        return bsearch(mid+1, high)


x = bsearch(1,n)
# log(x)
print(x)

n = int(input())

l = 0
r = n

def eats(n, k):
	res = 0
	while n > 0:
		if n < k:
			res += n
			n = 0
		else:
			res += k
			n -= k
			n -= n//10
	return res

while r-l > 1:
	mid = (r + l) // 2
	if eats(n, mid) >= (n+1) // 2:
		r = mid
	else:
		l = mid

print(r)


DEBUG = True
n = input().strip().split(" ")
n = int(n[0])

def oneTest(N, k):
    n = N

    nv = 0
    np = 0

    while n > 0:
        if n <= k:
            nv += n
            n = 0
        else:
            n -= k
            nv += k

            x = n // 10
            n -= x
            np += x

    assert nv + np == N
    return nv * 2 >= N


def getResult(n):
    lo = 1
    hi = n
    while lo < hi:
        mid = (lo + hi) // 2
        if not oneTest(n, mid):
            lo = mid + 1
        else:
            hi = mid
    return lo


k = getResult(n)
print(k)

if DEBUG:
    if k > 1:
        assert not oneTest(n, k-1)
    assert oneTest(n, k)
    assert oneTest(n, k+1)


n=int(input())
def f(k):
 s=(n+1)//2;m=n
 while s>0and m:
  l=min(k,m);s-=l;m-=l;m-=m//10
 return s<=0
l=[1,1]
if not f(1):
 l[1]=n//2
 while l[1]-l[0]>1:
  m=sum(l)//2
  l[f(m)]=m
print(l[1])

n = int(input())
left = 1
right = n

def modulate(k):
    e = n
    Vasya = 0
    Petya = 0
    while e > 0:
        #print(e)
        if e <= k:
            Vasya += e
            break
        diff = e - k
        Vasya += k
        e -= k
        if e >= 10:
            Petya +=  diff // 10
            e -= diff // 10
        #print(e, ' left')
    #print(Vasya, 'ate Vasya overall')
    #print(Petya, 'ate Petya overall')
    if Vasya >= Petya:
        return True
    else:
        return False

while right - left > 1:
    middle = (right + left) // 2
    if not modulate(middle):
        left = middle
    else:
        right = middle

if modulate(left):
    print(left)
else:
    print(right)