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: MEDIUM_HARD
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
import sys
n = int(sys.stdin.readline().rstrip('\n'))
if n < 5:
	res = n * (n - 1) // 2
	print(res)
	exit(0)
sum = n + (n - 1)
l = len(str(sum))
if str(sum) == l * '9':
	print(1)
	exit(0)
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)


import sys
input = sys.stdin.buffer.readline
n = input().strip()
n2 = int(n)
mx = str(n2 + n2 - 1)
if mx.count('9') == len(mx):
	print(1)
elif int(mx) < 9:
	print(n2 * (n2 - 1) // 2)
else:
	ans = 0
	mx = int(mx)
	nines = '9' * (len(str(mx)) - 1)
	for i in range(0, 9):
		curr = int(str(i) + nines)
		if curr > mx:
			break
		elif curr <= n2 + 1:
			ans += curr // 2
		else:
			ans += curr // 2 - (curr - 1 - n2)
	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:
		suf = '9' * (len_n - 1)
		k = int(suf)
		res = 0
		for c in range(10):
			if int(str(c) + suf) <= 2 * n - 1:
				if int(str(c) + suf) <= n:
					for i in range(c // 2 + 1):
						if i == c - i:
							if i == 0:
								res += (k - 1) // 2
							else:
								res += (k + 1) // 2
						elif i == 0:
							res += k
						else:
							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:
									res += (k - 1) // 2
								else:
									res += (k + 1) // 2
							elif i == 0:
								res += k
							else:
								res += k + 1
						elif i != c - i:
							res += n - int(str_n[0]) * (k + 1) + 1
						else:
							_n = int(str_n[1:])
							res += get_answer(_n) + (_n in nine)
			else:
				break
		return res
	else:
		suf = int('9' * len_n)
		return n - (suf + 1) // 2 + 1
print(get_answer(int(input())))


import bisect

def list_output(s):
	print(' '.join(map(str, s)))

def list_input(s='int'):
	if s == 'int':
		return list(map(int, input().split()))
	elif s == 'float':
		return list(map(float, input().split()))
	return list(map(str, input().split()))
n = int(input())
seq = str(n)
l = len(seq)
if n < 5:
	print(n * (n - 1) // 2)
	exit(0)
smax = n + (n - 1)
if str(smax) == '9' * l:
	print('1')
	exit(0)
res = 0
l2 = len(str(smax))
s = 10 ** (l2 - 1) - 1
while s <= smax:
	if n >= s:
		res += s // 2
	else:
		res += n - s // 2
	s += 10 ** (l2 - 1)
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)
	exit(0)
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)


import sys
input = sys.stdin.readline

def solve(n, k):
	l = max(1, k - n)
	r = min(k - 1, n)
	return max(r - l + 1, 0)
z = int(input())
count = 0
lol = 2 * z - 1
lol += 1
while lol > 0:
	lol = lol // 10
	count += 1
count -= 1
ok = pow(10, count) - 1
ans = 0
if ok == 0:
	for i in range(10):
		po = solve(z, i)
		if i % 2 == 0:
			ans += po // 2
		else:
			ans += (po + 1) // 2
	print(ans)
	quit()
for i in range(10):
	if ok + pow(10, count) * i <= 2 * z - 1:
		ans = ans + solve(z, ok + pow(10, count) * i)
print(ans // 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)


n = int(input())
m = n
digits = 0
while m > 0:
	m //= 10
	digits += 1
if n < 5:
	print(n * (n - 1) // 2)
	exit()
if n == 10 ** digits - 1:
	print(n // 2)
	exit()
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)


n = int(input())
maxNine = len(str(n * 2)) - 1
base = int(10 ** maxNine)
count = n // base
remainder = n % base
res = 0
if maxNine == 0:
	res = n * (n - 1) // 2
elif remainder * 2 < base:
	res = (count + 1) * remainder * count + count * count * (base // 2 - remainder)
else:
	bonusCount = remainder - base // 2 + 1
	res = (count + 1) * (count + 1) * bonusCount + (count + 1) * count * (base // 2 - bonusCount)
	res -= (n + 1) // base
print(res)


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


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:
			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()


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)


n = int(input())
lim = n + n - 1
R = 0
m = 0
while m <= lim:
	m = m * 10 + 9
	R += 1
m //= 10
inc = m + 1
if m == 0:
	print(n * (n - 1) // 2)
	import sys
	sys.exit(0)
s = 0
while True:
	low = m - n
	if low > n:
		break
	fix = 0
	if low <= 0:
		fix = -low + 1
	lo = low + fix
	hi = n - fix
	toadd = (hi - lo + 1) // 2
	s += toadd
	m += inc
print(s)


n = int(input())
if n < 5:
	print(n * (n - 1) // 2)
	exit()
s0 = str(n + n - 1)
k = len(s0)
if s0 != k * '9':
	k -= 1
s = k * '9'

def cnt(s):
	v = int(s)
	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())
x = 2 * n - 1
o = len(str(x)) * '9'
if x == int(o):
	print(1)
	exit(0)
if n < 5:
	print(n * (n - 1) // 2)
	exit(0)
o = o[1:]
ans = 0
for i in range(9):
	r = str(i) + o
	r = int(r)
	if r <= n + 1:
		ans += r // 2
	elif r <= x:
		ans += (x - r) // 2 + 1
print(ans)


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 = input()
if n == '9' * len(n):
	print(int(n) // 2)
	quit()
p = (len(str(int(n) * 2)) - 1) * '9'
if p == '':
	print((int(n) * int(n) - int(n)) // 2)
	quit()
ans = 0
f = 0
while int(str(f) + p) < 2 * int(n):
	k = int(str(f) + p)
	ans += min(k // 2, int(n) - k // 2)
	f += 1
print(ans)


n = int(input())

def length(obj):
	return len(str(obj))

def num_nine(num):
	i = 0
	j = 9
	while num >= j:
		i += 1
		j += 9 * 10 ** i
	return i

def split():
	blocks = (n + 1) // count
	extra = (n + 1) % count
	b = blocks // 2
	f = blocks - b
	return [f, b, extra]

def ans():
	if nines == 0:
		return int(n * (n - 1) / 2)
	if n == 10 ** nines - 1:
		return n - 10 ** nines // 2
	if lent == nines:
		return n - 10 ** nines // 2 + 1
	ls = split()
	return ls[0] * ls[1] * count - ls[1] + ls[0] * ls[2]
num = 2 * n - 1
lent = length(n)
nines = num_nine(num)
count = 10 ** nines // 2
print(ans())


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))))


from math import log10, floor
n = int(input())
if n < 5:
	print(n * (n - 1) // 2)
else:
	base = floor(log10(n / 5)) + 1
	nines = sum((9 * 10 ** i for i in range(base)))
	result = 0
	adding = 0
	for i in range(9):
		target = nines * (i + 1) + i
		if target // 2 < n < target:
			result += n - target // 2
		elif n >= target:
			result += target // 2
	print(result)


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

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

def map_string():
	return input().split()
n = int(input())
mx = len(str(n + n)) - 1
ad = 10 ** mx
cur = ad - 1
ans = 0
for i in range(10):
	lol = n + n - 1
	if lol < cur:
		break
	x = cur - n
	if x >= 1:
		ans += (n - x + 1) // 2
	else:
		x = cur - 1
		ans += x // 2
	cur += ad
if n >= 5:
	print(ans)
else:
	print(n * (n - 1) // 2)


def max9s(n):
	for i in range(10, 0, -1):
		if n + (n - 1) >= 10 ** i - 1:
			return i
	return 0

def calcNums(tgt, n):
	iniP = max(1, tgt - n)
	(ini, fin) = (iniP, min(tgt, n) - 1)
	while ini < fin:
		piv = (ini + fin) // 2 + 1
		if tgt - piv >= piv + 1:
			ini = piv
		else:
			fin = piv - 1
	if fin < ini or 2 * ini + 1 > tgt:
		return 0
	return ini - iniP + 1

def testCase(n):
	ncs = max9s(n)
	ans = 0
	for i in range(10):
		ans += calcNums((i + 1) * 10 ** ncs - 1, n)
	return ans
print(testCase(int(input())))


import sys
input = sys.stdin.buffer.readline
import os
from math import *

def func(x):
	if n >= x:
		val = (x - 1) // 2
	else:
		val = (n + n + 1 - x) // 2
	return max(0, val)
n = int(input())
x = [0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999, 9999999999]
s = n + n - 1
if x[len(str(s))] == s:
	print('1')
else:
	ans = 0
	k = x[len(str(s))] // 10
	for i in range(0, 10):
		if i * (k + 1) + k <= s:
			ans += func(i * (k + 1) + k)
		else:
			break
	print(ans)


n = int(input())

def spades(n):
	i = 0
	while 10 ** i <= n:
		i += 1
	upper = 10 ** i
	if n >= upper // 2:
		R = i
	else:
		R = i - 1
	base = 10 ** R - 1
	count = 0
	if base == 0:
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if i != j:
					count += 1
	else:
		count = 0
		for j in range(10):
			goal = j * (base + 1) + base
			l = max(1, goal - n)
			r = min(goal - 1, n)
			if r - l + 1 >= 0:
				count += r - l + 1
	print(count // 2)
spades(n)


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)


n = int(input())
if n < 5:
	print(n * (n - 1) // 2)
	exit()
lim = int(500000000.0)
while lim > n:
	lim //= 10
curr_step = lim * 10 // 5
curr_batch = (n - lim) // curr_step + 1
distance = curr_batch * (curr_batch - 1) // 2 * curr_step
rem_distance = (n - (lim + curr_step * (curr_batch - 1)) + 1) * curr_batch
delay = (n - curr_step + 1) // curr_step + 1
res = distance + rem_distance - delay
print(res)


n = int(input())
if n < 5:
	print(n * (n - 1) // 2)
else:
	x = n + n - 1
	if str(x).count('9') == len(str(x)):
		print(1)
	else:
		ans = 0
		x = len(str(x))
		x = x - 1
		z = 10 ** x
		y = int('9' * x)
		while y <= n + (n - 1):
			if n >= y:
				ans += y // 2
			else:
				ans += n - y // 2
			y += z
		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)


n = int(input())
mx = 2 * n - 1
mx_old = mx
digits = 0
all_nines = True
while mx > 0:
	digits += 1
	if mx % 10 != 9:
		all_nines = False
	mx //= 10
if all_nines:
	print(1)
	exit()
if digits == 1:
	print(n * (n - 1) // 2)
	exit()
s = int('9' * (digits - 1))
d = 10 ** (digits - 1)
ans = 0
while d > 1 and s + d <= mx_old:
	if s == n:
		ans += n - s // 2 - 1
	else:
		ans += min(s // 2, n - s // 2)
	s = s + d
if s == n:
	ans += n - s // 2 - 1
else:
	ans += n - s // 2
print(ans)


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
s = len(str(n))
if n < 5:
	print(n * (n - 1) // 2)
elif 2 * n == 10 ** s - 1:
	print(1)
else:
	nn = 5
	while n >= nn * 10:
		nn *= 10
	ans = 0
	temp = nn
	while temp <= n:
		ans += min(n - (temp - 1), temp - 1)
		temp += nn
	print(ans)


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)


def solve(x, a):
	if x < a:
		ans = 2 * x - a + 1
		ans //= 2
	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)


n = int(input())
if n <= 4:
	print(int(n * (n - 1) / 2))
else:
	v = 9
	dig = 10
	x = n * 2 - 1
	while v + dig * 9 <= x:
		v += dig * 9
		dig *= 10
	ans = 0
	f = True
	while f:
		f = False
		y = v // 2
		pairs = y - max(0, v - n - 1)
		if pairs > 0:
			f = True
			ans += pairs
		v += dig
		if n * 2 - 1 < v:
			break
	print(ans)


n = int(input())
l = 9
k = 0
while True:
	p = l // 2 + 1
	if n >= p:
		k += 1
		l = l * 10 + 9
	else:
		break
if k == 0:
	print(n * (n - 1) // 2)
else:
	l = '9' * k
	l = int(l)
	z = l + 1
	cnt = 0
	for i in range(9):
		p = z * i + l
		q = p // 2 + 1
		if n >= p:
			cnt += (p - 1) // 2
		elif n >= q:
			x = n - (p - n) + 1
			cnt += x // 2
		else:
			break
	print(cnt)


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))


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())
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)


n = int(input())
if n <= 4:
	print(n * (n - 1) // 2)
	exit(0)
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)


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())
import sys
num9 = len(str(2 * n)) - 1
s = [str(i) for i in range(10)]
ans = 0
if num9 == 0:
	print(n * (n - 1) // 2)
	sys.exit()
for i in s:
	x = i + '9' * num9
	x = int(x)
	ans += max(0, min(n - x // 2, x // 2))
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(result)


import math
n = int(input())
if n < 5:
	print(n * (n - 1) // 2)
	exit()
a = 0
k = int(math.log10(2 * n))
for i in range(k):
	a = a * 10 + 9
ans = 0
for i in range(9):
	r = int(str(i) + str(a))
	if r > 2 * n - 1:
		break
	elif r < 1 + n:
		ans += r // 2
	elif r < 2 * n:
		ans += (n - r + n + 1) // 2
print(ans)


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):
	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)


from sys import stdin, stdout, maxsize
R = lambda : stdin.readline().strip()
RL = lambda f=None: list(map(f, R().split(' '))) if f else list(R().split(' '))
output = lambda x: stdout.write(str(x) + '\n')
output_list = lambda x: output(' '.join(map(str, x)))
n = int(R())
if 2 * n - 1 < 9:
	print(n * (n - 1) // 2)
	exit()
num = 9
pw = 1
while 9 * 10 ** pw + num <= 2 * n - 1:
	num = 9 * 10 ** pw + num
	pw += 1
ans = 0
for i in range(10):
	x = i * 10 ** pw + num
	if x <= 2 * n - 1:
		cnt = min(x, n) - max(1, x - min(x, n)) + 1
		ans += cnt - cnt % 2
	else:
		break
print(ans // 2)


from math import *
import sys
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
		p += c + 1
	return res
print(solve(n))