Submarine in the Rybinsk Sea (hard edition)
设$x = \overline{x_px_{p-1}\cdots x_{0}},y = \overline{y_qy_{q-1}\cdots y_{0}}$
当$p>q$时,函数$f(x,y) = x_p\cdots x_qy_qx_{q-1}y_{q-1}\cdots x_0y_0$
当$p<=q$时,函数$f(x,y) = x_q\cdots x_py_px_{p-1}y_{p-1}\cdots x_0y_0$
现在给出一个长度为$n$的数组$a$,$a_i\le 1e^9, n\le 100000$
求$\sum \limits_{x=1}^{n} \sum \limits_{j=1}^{n} f(a_i, a_j)$