官方题解在干什么啊？？？

首先注意到一个数如果位数能更小，取更小总是更优的。

那么具体能多小呢？

首先，显然如果 $a$ 的位数 $>b$ 的位数，则有 $a>b$。设 $w_i$ 为 $a_i$ 的位数，则显然有 $w_i\le w_{i+1}$。

紧接着，考虑到如果位数是相同的，则 $a,b$ 的大小关系和它们的字典序大小关系一致。于是如果有 $p_i>p_{i+1}$，则有 $w_i+1=w_{i+1}$。

求出 $w_i$ 后，直接按找字典序贪心地取最小字典序即可。正确性显然：

• 依据 $w_i$ 的构造，可以保证 $a_i<a_{i+1}$；
• 由于单个数时 $w_i$ 相同，故字典序最小时就是最小的。

那么如何取最小字典序？这一个数的 $w$ 比前面的大，那么直接补 $0$ 即可；否则，需要在最后一位上 $+1$。前面的位都不用变。

可以直接单调栈维护，时间复杂度 $O(n)$，把 std 的四毛子 $O(n)$ 按在地上摩擦。

进制数 $10^{18} - 39$ 实在是太大了，因此位数多了就一定不是最优的，考虑确定每个数的位数：

• $a_{i + 1}$ 的位数不少于 $a_i$。
• 若 $p_i > p_j$ 且 $i < j$，则 $a_{p_i}$ 的位数一定严格多于 $a_{p_j}$。

由以上两条结论可以计算每个数的最少位数，并且可以证明最优解一定都取这样算出来的位数：假设 $a_i$ 是第一个不取算出来的位数的数字，由于 $a_{i + 1}$ 的位数与 $a_i$ 的位数的差值的最小值也是确定的（若排列 $p$ 中 $i + 1$ 排在 $i$ 前面则为 $1$，否则为 $0$），而原方案全部取到了最小差值，因此最后 $a_n$ 的位数一定大于原方案的位数，因此不是最优的。

接下来为每个数的每一位填写数字：设当前正在填写字典序排序的序列中 $[l, r]$ 位置内第 $t$ 高位及以后的值，则其中的 $t$ 位数至少依次填写为 $0, 1, \ldots$（如果 $a_{p_l}$ 不是 $t$ 位数，起点要加上 $1$；如果 $t = 1$，起点也要加上 $1$；如果都有，起点要加上 $2$），且 $a_{p_l}, a_{p_{l + 1}}, \ldots, a_{p_r}$ 的这一位必须单调不降。填完之后，只需要对其中每个第 $t$ 位相同的区间递归处理子区间即可。

在递归过程中对不存在 $t$ 位数的 $t$ 直接跳过，最终的时间复杂度为 $O(n \log n)$，空间复杂度为 $O(n)$（如果使用线段树实现 RMQ），瓶颈在跳过不合法 $t$ 使用的 RMQ。

（实际上，我们也可以套用 $O(n)-O(1)$ RMQ 把时间复杂度降到 $O(n)$，但是意义不大。）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 12, M = 17, B = 10, P = 1e9 + 7;
int p[N], q[N], d[N], b[N], w[N];
long long s[N][M];
pair <int, int> dfs(int l, int r, int n, int c, int e)
{
	if (l > r) return make_pair(0, 0);
	if (l == r) return make_pair((int) (1ll * e * b[d[p[l]] - c] % P), b[d[p[l]] - c]);
	long long u = 0, v = 0;
	int z = w[r - l + 1], t = min(s[l][z], s[r - (1 << z) + 1][z]) / n;
	if (d[p[l]] == t)
	{
		u = e;
		v = b[t - c];
		l++;
	}
	while (l <= r)
	{
		int z = w[r - l + 1];
		long long y = min(s[l][z], s[r - (1 << z) + 1][z]);
		if (y / n != t) break;
		pair <int, int> x = dfs(l, y % n, n, t + 1, 0);
		u = (u + x.first + 1ll * e * (1ll * B * x.second % P + 1) + 1) % P;
		v = (v + 1ll * b[t - c] * (1ll * B * x.second % P + 1)) % P;
		l = y % n + 2;
		e++;
	}
	pair <int, int> x = dfs(l, r, n, t + 1, 0);
	u = (u + x.first + 1ll * e * B % P * x.second % P) % P;
	v = (v + 1ll * b[t - c] * B % P * x.second % P) % P;
	return make_pair(u, v);
}
int main()
{
	freopen("seminar.in", "r", stdin);
	freopen("seminar.out", "w", stdout);
	int n;
	cin >> n;
	for (int i = 0, j = 1; j <= n; i++, j <<= 1)
		w[j] = i;
	for (int i = 3; i <= n; i++)
		if (!w[i]) w[i] = w[i - 1];
	b[0] = 1;
	for (int i = 1; i <= n; i++)
		b[i] = 1ll * b[i - 1] * B % P;
	for (int i = 1; i <= n; i++)
		cin >> p[i];
	for (int i = 1; i <= n; i++)
		q[p[i]] = i;
	d[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		d[i] = d[i - 1];
		if (q[i] < q[i - 1]) d[i]++;
	}
	for (int i = 1; i <= n; i++)
		s[i][0] = 1ll * d[p[i]] * n + i - 1;
	for (int j = 1; (1 << j) <= n; j++)
		for (int i = 1; i + (1 << j) - 1 <= n; i++)
			s[i][j] = min(s[i][j - 1], s[i + (1 << (j - 1))][j - 1]);
	cout << dfs(1, n, n, 1, 1).first << endl;
	return 0;
}