H. Kickoff Countdown (Hard)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

(The only difference between the easy and hard versions is the constraint on $$$n$$$.)

It's game day, and students are in DKR, eagerly watching the scoreboard clock counting down to kickoff. The countdown is displayed as $$$n$$$ mechanical flip-digit indicators, each showing a digit from $$$0-9$$$.

The clock is weird; when the display ticks down from $$$t$$$ to $$$t-1$$$, the digits do not flip all instantly. Instead, each digit that needs to change takes 1 second to flip. But digits can only be flipped once at a time.

So, for instance, if the clock ticks down from $$$\mathbf{67}$$$ to $$$\mathbf{66}$$$, it only takes 1 second, as only one digit changed. But if the clock ticks down from $$$\mathbf{900}$$$ to $$$\mathbf{899}$$$, it takes 3 seconds, as three digits changed.

Given how many seconds are currently displayed on the clock, the students are wondering how many actual seconds it will take until kickoff (when the clock has all digits showing $$$0$$$).

Input

The first line will contain $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, the number of digits of the number.

The second line will be a string of $$$n$$$ digits, the current display on the clock. It is guaranteed that at least one digit is not zero.

Output

Print a single integer without leading zeros, the number of actual seconds left until kickoff. Note that this number can be huge.

Examples
Input
2
67
Output
73
Input
3
003
Output
3
Input
5
12345
Output
13715
Input
1
1
Output
1
Input
30
116605222020078348307278321906
Output
129561357800087053674753690995
Note

In the first example, there are 6 changes that take 2 seconds: $$$60$$$ to $$$59$$$, $$$50$$$ to $$$49$$$, $$$40$$$ to $$$39$$$, $$$30$$$ to $$$29$$$, $$$20$$$ to $$$19$$$, and $$$10$$$ to $$$09$$$. So, the total time is $$$2(6) + 1(67-6) = 73$$$.