Prof. Vasechkin wants to represent positive integer *n* as a sum of addends, where each addends is an integer number containing only 1s. For example, he can represent 121 as 121=111+11+–1. Help him to find the least number of digits 1 in such sum.
The first line of the input contains integer *n* (1 ≤ *n* &lt; 10<sup class="upper-index">15</sup>).
from array import array

n = int(input())
stk, ans = [(n, 0)], 10 ** 18
ones = [int('1' * x) for x in range(1, 17)]

while stk:
    cur, steps = stk.pop()
    ix = 0
    for j in range(len(ones) - 1, -1, -1):
        if ones[j] < cur:
            ix = j
            break

    div, mod = divmod(cur, ones[ix])
    if mod == 0:
        ans = min(ans, div * len(str(ones[ix])) + steps)
    else:
        stk.append((mod, div * len(str(ones[ix])) + steps))

    cur = ones[ix + 1] - cur
    div, mod = divmod(cur, ones[ix])
    steps += len(str(ones[ix + 1]))

    if mod == 0:
        ans = min(ans, div * len(str(ones[ix])) + steps)
    else:
        stk.append((mod, div * len(str(ones[ix])) + steps))

print(ans)
