Little Sofia is in fourth grade. Today in the geometry lesson she learned about segments and squares. On the way home, she decided to draw $n$ squares in the snow with a side length of $1$. For simplicity, we assume that Sofia lives on a plane and can draw only segments of length $1$, parallel to the coordinate axes, with vertices at integer points.

In order to draw a segment, Sofia proceeds as follows. If she wants to draw a vertical segment with the coordinates of the ends $(x, y)$ and $(x, y+1)$. Then Sofia looks if there is already a drawn segment with the coordinates of the ends $(x', y)$ and $(x', y+1)$ for some $x'$. If such a segment exists, then Sofia quickly draws a new segment, using the old one as a guideline. If there is no such segment, then Sofia has to take a ruler and measure a new segment for a long time. Same thing happens when Sofia wants to draw a horizontal segment, but only now she checks for the existence of a segment with the same coordinates $x$, $x+1$ and the differing coordinate $y$.

For example, if Sofia needs to draw one square, she will have to draw two segments using a ruler:  [Image] 

After that, she can draw the remaining two segments, using the first two as a guide:  [Image] 

If Sofia needs to draw two squares, she will have to draw three segments using a ruler:  [Image] 

After that, she can draw the remaining four segments, using the first three as a guide:  [Image] 

Sofia is in a hurry, so she wants to minimize the number of segments that she will have to draw with a ruler without a guide. Help her find this minimum number.


-----Input-----

The only line of input contains a single integer $n$ ($1 \le n \le 10^{9}$), the number of squares that Sofia wants to draw.


-----Output-----

Print single integer, the minimum number of segments that Sofia will have to draw with a ruler without a guide in order to draw $n$ squares in the manner described above.


-----Examples-----
Input
1

Output
2

Input
2

Output
3

Input
4

Output
4

Difficulty: interview

Starter code:

Solutions:
n = int(input())

a = b = 1

while a * b < n:
    if a < b:
        a += 1
    else:
        b += 1

print(a+b)


n = int(input())
l = 0
r = n
while r - l > 1:
    m = (l + r) // 2
    if m * m >= n:
        r = m
    else:
        l = m
if (r - 1) * r >= n:
    print(2 * r - 1)
else:
    print(2 * r)


n = int(input())
w, h = 0, 0
width = True
while w * h < n:
    if width:
        w += 1
    else:
        h += 1
    width = not width
print(w + h)


n = int(input())
i = 0
while (i + 1) * (i + 1) <= n:
	i += 1
print(2 * i + (n - i * i + i - 1) // i)


from math import ceil
n = int(input())
c = ceil(n ** 0.5)
print(c + (n + c - 1)//c)

import math
n = int(input())
ans = 10 ** 9 + 7
for i in range(1, int(math.sqrt(n)) + 1):
    if n % i == 0:
        ans = min(ans, i + n // i)
    else:
        ans = min(ans, i + n // i + 1)
print(ans)


n = int(input())
ans = []
for i in range(1, 100000):
    ans.append(i + (n - 1) // i + 1)
print(min(ans))

n = int( input() )

a = 0
b = 0

while a * b < n:
    if a == b:
        a += 1
    else:
        b += 1

print( a + b )


from math import sqrt
n = int(input())
x = int(sqrt(n))
x = max(0,x-5)
ans = n+1
for i in range(x,x+11):
    for j in range(x,x+11):
        if i*j >= n:
            ans = min(ans,i+j)
print(ans)            


def ii():
    return int(input())
def mi():
    return list(map(int, input().split()))
def li():
    return list(mi())

n = ii()
for i in range(1, n + 1):
    if i * i > n:
        break
i -= 1
ans = 2 * i
if n - i * i == 0:
    pass
elif n - i * i <= i:
    ans += 1
else:
    ans += 2
print(ans)


from math import ceil
n = int(input())
a = ceil(n**0.5)
print(a + ceil(n/a))

from math import *
from itertools import *
from collections import *
from functools import reduce


def input_ints():
    return list(map(int, input().split()))


def input_floats():
    return list(map(float, input().split()))


def input_strings():
    return input().split()


# Solution written by john21

n = int(input())

a = ceil(sqrt(n))
b = ceil(n/a)

print(a+b)


from math import sqrt

n = int(input())
sq = int(sqrt(n))
s = sq * sq
if n == s:
    print(2 * sq)
elif n <= s + sq:
    print(2 * sq + 1)
else:
    print(2 * sq + 2)

n = int(input())
t = 0
while 1:
    t += 1
    if (t//2)*(t-t//2) >= n:
        print(t)
        break

import math

n = int(input())
sq = int(math.sqrt(n))
dif = n - sq * sq
add = 0
if dif > sq:
    add = 2
elif dif != 0:
    add = 1
print(2 * sq + add)


n = int(input())
s = 0
while s*s <= n:
    s += 1
s -= 1
if n == s*s:
    print(2*s)
    return

d = n-s*s
from math import ceil
print(2*s + ceil(d*1./s))


n = int(input())

a = b = 1
while a * b < n:
    if a == b:
        a += 1
    else:
        b += 1

print(a+b)


n = int(input())
j = int(n ** 0.5)

if n == j ** 2:
    print(2 * j)
elif n <= j * (j + 1):
    print(2 * j + 1)
else:
    print(2 * j + 2)

def sq(x):
    s = int(x**0.5)
    for i in range(1, -2, -1):
        ts = s + i
        if ts**2 <= x:
            return ts

n = int(input())
s = sq(n)

if s**2 == n:
    print(s * 2)
elif (s + 1) * s >= n:
    print(s * 2 + 1)
else:
    print(s * 2 + 2)



def getS(n):
    return int(n ** (1/2)) 

squares = int(input())


ans = 0

    
side = getS(squares)
ans += side * 2

remains = squares - (side ** 2)

if remains % side == 0:
    ans += remains // side
else:
    ans += remains // side + 1

print(ans)

n=int(input())
i=1
while i**2<n:
    i+=1
if n%i==0:
    print(i+n//i)
else:
    print(i+n//i+1)


n = int(input())
i = 1
j = 1
k = 0
while (i * j < n):
    if k % 2 == 0:
        i += 1
    else:
        j += 1
    k = 1 - k
print(i+j)

while True:
    n = int(input())

    sqrt_n = int(n**0.5)

    minn = 100000000

    if(sqrt_n*sqrt_n >= n):

        minn = min(minn, sqrt_n + sqrt_n)

    if(sqrt_n*(sqrt_n+1) >= n):

        minn = min(minn, sqrt_n + (sqrt_n+1))

    if((1+sqrt_n)*(1+sqrt_n) >= n):

        minn = min(minn, (1+sqrt_n) + (1+sqrt_n))

    print(minn)

    break


import math
n=int(input())
a=int(math.sqrt(n))
if a*a<n:
    a+=1
b=math.ceil(n/a)
print(a+b)