Submarine in the Rybinsk Sea (hard edition)
Contest: Codeforces Round 574 (Div. 2)
Difficulty rating: 1800
Tags: combinatorics, math, number theory

This problem differs from the previous one only in the absence of the constraint on the equal length of all numbers $$$a_1, a_2, \dots, a_n$$$.

A team of SIS students is going to make a trip on a submarine. Their target is an ancient treasure in a sunken ship lying on the bottom of the Great Rybinsk sea. Unfortunately, the students don't know the coordinates of the ship, so they asked Meshanya (who is a hereditary mage) to help them. He agreed to help them, but only if they solve his problem.

Let's denote a function that alternates digits of two numbers $$$f(a_1 a_2 \dots a_{p - 1} a_p, b_1 b_2 \dots b_{q - 1} b_q)$$$, where $$$a_1 \dots a_p$$$ and $$$b_1 \dots b_q$$$ are digits of two integers written in the decimal notation without leading zeros.

In other words, the function $$$f(x, y)$$$ alternately shuffles the digits of the numbers $$$x$$$ and $$$y$$$ by writing them from the lowest digits to the older ones, starting with the number $$$y$$$. The result of the function is also built from right to left (that is, from the lower digits to the older ones). If the digits of one of the arguments have ended, then the remaining digits of the other argument are written out. Familiarize with examples and formal definitions of the function below.

For example: $$$$$$f(1111, 2222) = 12121212$$$$$$ $$$$$$f(7777, 888) = 7787878$$$$$$ $$$$$$f(33, 44444) = 4443434$$$$$$ $$$$$$f(555, 6) = 5556$$$$$$ $$$$$$f(111, 2222) = 2121212$$$$$$

Formally,

- if $$$p \ge q$$$ then $$$f(a_1 \dots a_p, b_1 \dots b_q) = a_1 a_2 \dots a_{p - q + 1} b_1 a_{p - q + 2} b_2 \dots a_{p - 1} b_{q - 1} a_p b_q$$$;
- if $$$p < q$$$ then $$$f(a_1 \dots a_p, b_1 \dots b_q) = b_1 b_2 \dots b_{q - p} a_1 b_{q - p + 1} a_2 \dots a_{p - 1} b_{q - 1} a_p b_q$$$.

Mishanya gives you an array consisting of $$$n$$$ integers $$$a_i$$$, your task is to help students to calculate $$$\sum_{i = 1}^{n}\sum_{j = 1}^{n} f(a_i, a_j)$$$ modulo $$$998\,244\,353$$$.

Input format:
The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 100\,000$$$) — the number of elements in the array. The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.

Output format:
Print the answer modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
12 3 45

Example output:
12330

Example input:
2
123 456

Example output:
1115598

Editorial:
Let $$$cnt_{len}$$$ be the number of $$$a_i$$$ with length $$$len$$$. We will calculate each number's contribution in the answer separately.
When we calculate the contribution of the current number in the answer, let's iterate over all lengths $$$l$$$ from $$$1$$$ to $$$L$$$ where $$$L$$$ is the maximum length of some number in the array and add the following value to the answer: $$$cnt_{l} \cdot (fl_{a_i, l} + fr_{a_i, l})$$$.
The function $$$fl_{x, l}$$$ means that we merge the number $$$x$$$ with some (it does not matter) number of length $$$l$$$ and digits of $$$x$$$ will be on odd positions in the resulting number (except some leading digits which will be on odd and on even position as well). And the function $$$fr_{x, l}$$$ does almost the same thing but it counts digits of $$$x$$$ on even positions.
Time complexity is $$$O(n)$$$ with the constant factor $$$L^2$$$.