#include <iostream>
#include <cmath>
using int_t = long long;
constexpr int_t N = 1000000LL;
inline int sumDigits(int_t n, int dig, int& s)
{
auto even = !(dig % 2);
auto sum = 0;
for (; n; n /= 10, s = -s) sum += s * (n % 10);
return even ? -sum : sum;
}
inline int sumDigits(int_t n, int dig)
{
auto s = 1;
return sumDigits(n, dig, s);
}
inline int_t sub(int dig)
{
return dig == 1 ? 0 : static_cast<int_t>(std::pow(10.0, dig - 1));
}
inline int_t odd(int_t n, int dig)
{
return (n - sub(dig)) / 2 + ((n % 2) ? 1 : -sumDigits(n, dig));
}
inline int_t even(int_t n, int dig)
{
auto sum = 0LL, b = 0LL, z = 1LL, x = (n - sub(dig)) / 10;
for (auto s = -1; n; n /= 10, s = -s, x /= 10, z *= 10) {
int d = n % 10;
sum += s * ((x * 45 + (d * (d - 1) / 2)) * z + d * (b + 1));
b += d * z;
}
return sum;
}
int solve(int_t n)
{
auto sum = 0LL;
auto dig = static_cast<int>(std::floor(std::log10(n))) + 1;
if (dig > 1) sum = 5;
if (dig > 2) for (int i = 2, a = 45, s = -1; i < dig; ++i, a *= 10, s = -s) sum += a * s;
return sum + ((dig % 2) ? odd(n, dig) : -even(n, dig));
}
int main()
{
auto sign = 1;
auto testsum = 0LL;
for (auto i = 1LL; i < N; ++i) {
testsum += sumDigits(i, static_cast<int>(std::floor(std::log10(i))) + 1, sign);
if (solve(i) != testsum) {
std::cout << "Error! " << i << ": " << testsum << ", " << solve(i) << std::endl;
return 1;
}
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y21hdGg+Cgp1c2luZyBpbnRfdCA9IGxvbmcgbG9uZzsKY29uc3RleHByIGludF90IE4gPSAxMDAwMDAwTEw7CgppbmxpbmUgaW50IHN1bURpZ2l0cyhpbnRfdCBuLCBpbnQgZGlnLCBpbnQmIHMpCnsKCWF1dG8gZXZlbiA9ICEoZGlnICUgMik7CglhdXRvIHN1bSA9IDA7Cglmb3IgKDsgbjsgbiAvPSAxMCwgcyA9IC1zKSBzdW0gKz0gcyAqIChuICUgMTApOwoJcmV0dXJuIGV2ZW4gPyAtc3VtIDogc3VtOwp9CgppbmxpbmUgaW50IHN1bURpZ2l0cyhpbnRfdCBuLCBpbnQgZGlnKQp7CglhdXRvIHMgPSAxOwoJcmV0dXJuIHN1bURpZ2l0cyhuLCBkaWcsIHMpOwp9CgppbmxpbmUgaW50X3Qgc3ViKGludCBkaWcpCnsKCXJldHVybiBkaWcgPT0gMSA/IDAgOiBzdGF0aWNfY2FzdDxpbnRfdD4oc3RkOjpwb3coMTAuMCwgZGlnIC0gMSkpOwp9CgppbmxpbmUgaW50X3Qgb2RkKGludF90IG4sIGludCBkaWcpCnsKCXJldHVybiAobiAtIHN1YihkaWcpKSAvIDIgKyAoKG4gJSAyKSA/IDEgOiAtc3VtRGlnaXRzKG4sIGRpZykpOwp9CgppbmxpbmUgaW50X3QgZXZlbihpbnRfdCBuLCBpbnQgZGlnKQp7CglhdXRvIHN1bSA9IDBMTCwgYiA9IDBMTCwgeiA9IDFMTCwgeCA9IChuIC0gc3ViKGRpZykpIC8gMTA7Cglmb3IgKGF1dG8gcyA9IC0xOyBuOyBuIC89IDEwLCBzID0gLXMsIHggLz0gMTAsIHogKj0gMTApIHsKCQlpbnQgZCA9IG4gJSAxMDsKCQlzdW0gKz0gcyAqICgoeCAqIDQ1ICsgKGQgKiAoZCAtIDEpIC8gMikpICogeiArIGQgKiAoYiArIDEpKTsKCQliICs9IGQgKiB6OwoJfQoJcmV0dXJuIHN1bTsKfQoKaW50IHNvbHZlKGludF90IG4pCnsKCWF1dG8gc3VtID0gMExMOwoJYXV0byBkaWcgPSBzdGF0aWNfY2FzdDxpbnQ+KHN0ZDo6Zmxvb3Ioc3RkOjpsb2cxMChuKSkpICsgMTsKCWlmIChkaWcgPiAxKSBzdW0gPSA1OwoJaWYgKGRpZyA+IDIpIGZvciAoaW50IGkgPSAyLCBhID0gNDUsIHMgPSAtMTsgaSA8IGRpZzsgKytpLCBhICo9IDEwLCBzID0gLXMpIHN1bSArPSBhICogczsKCXJldHVybiBzdW0gKyAoKGRpZyAlIDIpID8gb2RkKG4sIGRpZykgOiAtZXZlbihuLCBkaWcpKTsKfQoKaW50IG1haW4oKQp7CglhdXRvIHNpZ24gPSAxOwoJYXV0byB0ZXN0c3VtID0gMExMOwoJZm9yIChhdXRvIGkgPSAxTEw7IGkgPCBOOyArK2kpIHsKCQl0ZXN0c3VtICs9IHN1bURpZ2l0cyhpLCBzdGF0aWNfY2FzdDxpbnQ+KHN0ZDo6Zmxvb3Ioc3RkOjpsb2cxMChpKSkpICsgMSwgc2lnbik7CgkJaWYgKHNvbHZlKGkpICE9IHRlc3RzdW0pIHsKCQkJc3RkOjpjb3V0IDw8ICJFcnJvciEgIiA8PCBpIDw8ICI6ICIgPDwgdGVzdHN1bSA8PCAiLCAiIDw8IHNvbHZlKGkpIDw8IHN0ZDo6ZW5kbDsKCQkJcmV0dXJuIDE7CgkJfQoJfQp9