There are n shovels in Polycarp's shop. The i-th shovel costs i burles, that is, the first shovel costs 1 burle, the second shovel costs 2 burles, the third shovel costs 3 burles, and so on. Polycarps wants to sell shovels in pairs.

Visitors are more likely to buy a pair of shovels if their total cost ends with several 9s. Because of this, Polycarp wants to choose a pair of shovels to sell in such a way that the sum of their costs ends with maximum possible number of nines. For example, if he chooses shovels with costs 12345 and 37454, their total cost is 49799, it ends with two nines.

You are to compute the number of pairs of shovels such that their total cost ends with maximum possible number of nines. Two pairs are considered different if there is a shovel presented in one pair, but not in the other.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 10^9) — the number of shovels in Polycarp's shop.


-----Output-----

Print the number of pairs of shovels such that their total cost ends with maximum possible number of nines. 

Note that it is possible that the largest number of 9s at the end is 0, then you should count all such ways.

It is guaranteed that for every n ≤ 10^9 the answer doesn't exceed 2·10^9.


-----Examples-----
Input
7

Output
3

Input
14

Output
9

Input
50

Output
1



-----Note-----

In the first example the maximum possible number of nines at the end is one. Polycarp cah choose the following pairs of shovels for that purpose:  2 and 7;  3 and 6;  4 and 5. 

In the second example the maximum number of nines at the end of total cost of two shovels is one. The following pairs of shovels suit Polycarp:  1 and 8;  2 and 7;  3 and 6;  4 and 5;  5 and 14;  6 and 13;  7 and 12;  8 and 11;  9 and 10. 

In the third example it is necessary to choose shovels 49 and 50, because the sum of their cost is 99, that means that the total number of nines is equal to two, which is maximum possible for n = 50.

Difficulty: interview

Starter code:

Solutions:
from sys import stdin as cin
from sys import stdout as cout

def main():
    n = int(cin.readline())
    o = 0
    for x in range(9, 0, -1):
        if 10 ** x // 2 <= n:
            ##print(x)
            for i in range(9):
                q = 10 ** x * (i + 1) // 2 - 1
                if q <= n:
                    o += min(q, n - q)
            print(o)
            return
    print(n * (n - 1) // 2)

main()


# python3
# utf-8

def solve(x, a):
    if x < a:
        ans = 2 * x - a + 1
        ans //= 2
        # return ans
    else:
        ans = (a - 1) // 2
    return max(0, ans)

n = input()
optimal_nines = len(n)
if int(n[0]) < 5:
    optimal_nines -= 1
n = int(n)
if n <= 4:
    print((n * (n - 1)) // 2)
    quit()
ans = 0
for i in range(0, 9):
    curr_num = str(i) + '9' * optimal_nines
    curr_num = int(curr_num)
    ans += solve(n, curr_num)

print(ans)


def f(w, n):
  if w >= 3 and w <= n + 1:
    return (w - 1) // 2
  elif w > n + 1 and w <= 2 * n - 1:
    return ((2 * n + 2) - w - 1) // 2
  else:
    return 0

n = int(input())
e = len(str(2 * n)) - 1
des = 10 ** e - 1
ans = 0
for i in range(1, 10):
  ans += f(i * 10 ** e - 1, n)
print(ans)

n=int(input())
if n<5:
    print(n*(n-1)//2)
    return
s0=str(n+n-1)
k=len(s0)
if s0!=k*'9':
    k-=1
s=k*'9'
def cnt(s):
    v=int(s)
    #print(v)
    if v>n*2-1:
        return 0
    if v==2*n-1:
        return 1
    if v>n:
        return n-v//2
    if v<=n:
        return v//2
ans=cnt(s)
for i in range(1,9):
    ans+=cnt(str(i)+s)
print(ans)

n = int(input())
if n < 5:
	print(n * (n-1) // 2)
	return
val = 5
while n >= val * 10:
	val *= 10
# print(val, nines)
ans = 0
_val = val
while _val <= n:
	ans += min(n - _val+1, _val - 1)
	_val += val
print(ans)

n = int(input())
max9 = 1
while (int('9' * max9) + 1) // 2 <= n:
    max9 += 1
max9 -= 1
k = 0
ans = 0
f = True
while f:
    number = int(str(k) + '9' * max9)
    b = min(number - 1, n)
    a = number // 2 + 1
    if a <= b:
        m = b - a + 1
        ans += m
        k += 1
    else:
        f = False

if n == 2:
    print(1)
elif n == 3:
    print(3)
elif n == 4:
    print(6)
else:
    print(ans)


# IAWT
n = int(input())
x = str(n + n - 1)
if x.count('9') == len(x):
    m = len(x)
else: m = len(x) - 1
m = '9' * m

def f(x): # Number of pairs with sum x
    if n+n-1 < x: return 0
    if x <= n:
        if x % 2 == 0: return max(x//2-1, 0)
        return x//2
    if x % 2 == 0:
        x //= 2
        return max(min(n - x, x - 1), 0)
    return max(min(n - x//2, x // 2), 0)

ans = 0
for i in range(9):
    s = int(str(i) + m)
    ans += f(s)

print(ans)



n = int(input())

biggest_num = 2 * n - 1

if all([x == '9' for x in str(biggest_num)]):
    lead_digit = 0
    length = len(str(biggest_num))
elif all([x == '9' for x in str(biggest_num)[1:]]):
    lead_digit = int(str(biggest_num)[0])
    length = len(str(biggest_num)) - 1
else:
    lead_digit = int(str(biggest_num)[0]) - 1
    length = len(str(biggest_num)) - 1


result = 0
for i in range(lead_digit + 1):
    desired_num = int(str(i) + '9' * length)
    if desired_num == 0: continue
    result += (min([n, desired_num - 1]) - max([desired_num // 2, desired_num - n]))
    #print(n - max([desired_num // 2, desired_num - n]))
    #print(n, desired_num // 2, desired_num - n)

    #print(desired_num, (min([n, desired_num - 1]) - max([desired_num // 2, desired_num - n])))

print(result)


n = int(input())
largest = n + n - 1
possible = [0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999, 999999999]
maximum9 = 0
indx1 = 0
i = 0
for p in possible:
  if p <= largest and p > maximum9:
    maximum9 = p
    indx1 = i
  i += 1
indx2 = 0
for i in range(9):
  if largest >= i*10**indx1+maximum9:
    indx2 = i
  else:
    break
count = 0
for i in range(indx2+1):
  count += max((2*min(n, i*10**indx1+maximum9-1)- max(1,i*10**indx1+maximum9)+1)//2, 0)
print(count)


from collections import Counter
n=int(input())
if n<5:
    d={2:1,3:3,4:6}
    print(d[n])
    return
z=len(str(n//5))
nn=5*10**(z-1)
n0=n-nn+1
if n0<nn:
    print(n0)
elif n0==nn:
    print(n0-1)
elif n0<=2*nn:
    print(n0-1)

elif n0<3*nn:
    print(n0*2-2*nn-1)
elif n0==3*nn:
    print(n0*2-2*nn-2)
elif n0<=4*nn:
    print(n0*2-2*nn-2)

elif n0<5*nn:
    print(n0*3-6*nn-2)
elif n0==5*nn:
    print(n0*3-6*nn-3)
elif n0<=6*nn:
    print(n0*3-6*nn-3)

elif n0<7*nn:
    print(n0*4-12*nn-3)
elif n0==8*nn:
    print(n0*4-12*nn-4)
elif n0<=8*nn:
    print(n0*4-12*nn-4)

elif n0<9*nn:
    print(n0*5-20*nn-4)
elif n0==9*nn:
    print(n0*5-20*nn-5)

from math import factorial as fac
def solve(n):
    if n <= 4:
        return fac(n) // (2 * fac(n - 2))
    m = n + (n - 1)
    x = '9'
    while(int(x + '9') <= m):
        x += '9'
    l = []
    for i in range(10):
        if int(str(i) + x) <= m:
            l.append(int(str(i) + x))
    res = 0
    for p in l:
        y = min(p - 1, n)
        res += (y - (p - y) + 1) // 2
    return res 
n = int(input())
print(solve(n))

n = int(input())
v = min(n, 5)
if v < 5:
    print(n*(n - 1) // 2)
    return
while v * 10 <= n:
    v *= 10
print(sum(min(n - i * v + 1, v * i - 1) for i in range(1, n // v + 1)))

n = int(input())
if n <= 4:
    print(n*(n-1)//2)
    return
a = 9
while int(str(a) + '9') <= 2*n - 1:
    a = int(str(a) + '9')
ans = 0
for i in range(0, 9):
    r = int(str(i) + str(a))
    if r > 2*n - 1:
        break
    ku = r - n
    if ku < 1:
        ans += r//2
    elif ku < n:
        ans += (n - ku + 1) // 2
print(ans)


from math import *
import sys
#sys.stdin = open('in.txt')

n =   int(input())

def closest9(n):
  s = '9'*(len(str(n+1))-1)
  return 0 if len(s) == 0 else int(s)

def solve(n):
  if n == 2: return 1
  if n == 3: return 3
  if n == 4: return 6
  s = n+n-1
  c = closest9(s)
  if c*10 + 9 == s: return 1
  p = c
  res = 0
  for i in range(10):
    if p <= n+1:
      res += p//2
    elif p > s:
      break
    else:
      res += 1+(s - p)//2
    #print(p, v)
    p += c+1
  return res

print(solve(n))



import sys

lines = []
for line in sys.stdin:
    lines.append(line)

n = int(lines[0].rstrip("\r\n\t "))

max_price = n * 2 - 1
nines = len(str(max_price + 1)) - 1

if nines < 1:
    cnt = 0
    for x in range(1, n):
        cnt += x
    print(cnt)
    return

price_suffix = "9"*nines
cnt = 0


def add_pairs(max_x: int, p: int):
    nonlocal cnt
    from_max = int(p / 2)
    to_max = p - 1
    if to_max > max_x:
        to_max = max_x
    from_min = p - to_max
    cnt += from_max - from_min + 1


for d in range(0, 10):
    if d > 0:
        price = int(str(d) + price_suffix)
    else:
        price = int(price_suffix)
    if price <= max_price:
        add_pairs(n, price)

print(cnt)



def check9(x):
	i = len(x) - 1
	while (i >= 0):
		if (x[i] != '9'):
			return len(x) - i - 1
		i -= 1
	return len(x) - i - 1

def solve(n):
	if (n < 5):
		return (n*(n-1)//2)
	res = 0
	x = str(n+n-1)
	length = len(x)

	if (check9(x) == length):
		return 1
	
	cur = '9'*(length-1)
	for i in range(9):
		c = str(i)
		p = int(c+cur)
		if (p <= n+1):
			res += p//2
		elif (p > n+n-1):
			res += 0
		else:
			res += 1 + (n + n - 1 - p)//2

	return res

n = int(input())

print(solve(n))



n = int(input())
le = len(str(n))
if n < 5:
    print((n * (n - 1)) // 2)
elif str(n).count('9') == le:
    print(n // 2)
else:
    if n + n - 1 < int('9'*le):
        le -= 1
    ans = 0
    s = '9'*le
    for i in range(9):
        t = str(i) + s
        t = int(t)
        if t <= n + 1:
            ans += t // 2
        elif t <= n + n - 1:
            ans += (1 + (n + n - 1 - t)//2)
    print(ans)


from sys import stdin, stdout

INF = float('inf')
n = int(stdin.readline())
count = [0, 5, 50, 500, 5000, 50000, 500000, 5000000, 50000000, 500000000, INF]

for label in range(len(count)):
    if count[label + 1] > n:
        break

pref = 0
value = int(str(pref) + '9' * label)
ans = 0

while value <= n - 1 + n:
    
    if n < 5:
        ans = n * (n - 1) // 2
        break
    
    k = max(value - n, 1)
    ans += (min(n, value - 1) - k + 1) // 2
    
    pref += 1
    value = int(str(pref) + '9' * label)

stdout.write(str(ans))

n = int(input())
a= 5
while a * 10 <= n:
    a *= 10
print(sum(min(n - i * a + 1, a * i - 1) for i in range(1, n // a + 1)) if n>=5 else n*(n-1)//2)

n = int(input())
a=5
while a*10<=n:a*=10
print(sum(min(n-i,i) for i in range(a-1,n,a)) if n>4 else n*(n-1)//2)

n = int(input())
m = 2*n-1
w = len(str(m+1))-1
ans = 0
for i in range(10):
	v = (i+1)*10**w - 1
	if 0 < v <= m:
		ans += (v-1)//2
		if v > n: ans -= v-n-1
print(ans)

nine = [0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999]


def get_answer(n):
    if (n < 5):
        return (n*(n-1))//2
    elif (2*n-1 in nine):
        return 1
    elif (n in nine):
        return (n-1)//2
    
    str_n = str(n)
    len_n = len(str_n)
    len_2n = len(str(2*n-1))
    
    if len_n == len_2n: # n < 50..0
        # pattern: A9..9, |9..9| = |n| - 1
        suf = "9" * (len_n - 1)
        k = int(suf)
        res = 0
        for c in range(10):
            if (int(str(c) + suf) <= 2*n-1):
                # print(str_n[0], c, '+', suf)
                if (int(str(c) + suf) <= n):
                    for i in range(c//2+1):
                        if i == c-i:
                            if i == 0:  # (0, 0): 01 -> 49
                                res += (k-1)//2
                            else:  # (1, 1): 00 -> 49
                                res += (k+1)//2
                        else:
                            if i == 0:  # (0, 1): 01 -> 99 
                                res += k
                            else:  # (1, 2): 00 -> 99
                                res += k+1
                else:
                    for i in range(c//2+1):
                        if i > int(str_n[0]) or c-i > int(str_n[0]):
                            continue
                        elif i < int(str_n[0]) and c-i < int(str_n[0]):
                            if i == c-i:
                                if i == 0:  # (0, 0): 01 -> 49
                                    res += (k-1)//2
                                else:  # (1, 1): 00 -> 49
                                    res += (k+1)//2
                            else:
                                if i == 0:  # (0, 1): 01 -> 99 
                                    res += k
                                else:  # (1, 2): 00 -> 99
                                    res += k+1
                        else:
                            # print(i, c-i, int(str(c) + suf), n)
                            if i != c - i:
                                # print(n-int(str_n[0])*(k+1)+1)
                                res += n-int(str_n[0])*(k+1)+1
                            else:
                                _n = int(str_n[1:])
                                # print(_n)
                                res += get_answer(_n) + (_n in nine)
                                # 99: (0, 0): 01 -> 49, (i, i): 00 -> 49 => +1
            else:
                break
        return res
    else: # n > 50..0
        # pattern: 9..9, |9..9| = |n|
        suf = int('9' * len_n)
        return n - (suf+1)//2 + 1

print(get_answer(int(input())))


n = int(input())
m = n

digits = 0
while m > 0:
    m //= 10
    digits += 1
if n < 5:
    print(n * (n - 1) // 2)
    return
if n == 10 ** digits - 1:
    print(n // 2)
    return
if n >= 5 * 10 ** (digits - 1):
    print(n - 5 * 10 ** (digits - 1) + 1) 
else:
    fst = int(str(n)[0])
    res = (fst) * (fst - 1) // 2 * 10 ** (digits - 1)
    res += (fst) * (10 ** (digits - 1) // 2 - 1)

    n = int(str(n)[1:])
    digits -= 1
    if n == 10 ** digits - 1:
        res += (n // 2)
    elif n >= 5 * 10 ** (digits - 1):
        res += (n - 5 * 10 ** (digits - 1) + 1)
    res += (n + 1) * fst 
    print(res)



import sys
n = int(sys.stdin.readline().rstrip("\n"))

if n < 5:
    res = n * (n-1) // 2
    print(res)
    return

sum = n + (n - 1)
l = len(str(sum))
if str(sum) == l * '9':
    print(1)
    return


res = 0
s = (l - 1) * '9'
for i in range(9):
    p = str(i) + s
    if int(p) <= n + 1:
        res += int(p) // 2
    elif int(p) > sum:
        break
    else:
        res += (1 + (sum - int(p)) // 2)
print(res)




s = input()
n = int(s)
num = '9'*len(s)
num = int(num)
if(2*n < num):
    num = num // 10
if (num == 0):
    print((n*(n-1)//2));
    return
ret = 0;
for i in range (9):
    tmp = str(i) + str(num)
    tmp = int(tmp);
    if (2 * n <= tmp):
        break;
    biggest = min(tmp - 1, n);
    smallest = tmp - biggest
    ret += (biggest - smallest + 1) // 2
print(ret)
# else :
#     biggest = min(num - 1, n);
#     smallest = num - biggest
#     print((biggest - smallest + 1) // 2)