Update：添加了时间复杂度的讲解，感谢 CleverPenguin 与 Starriverlight 的指正与不吝赐教。

一道很好的 trick 题，值得认真品味。

首先，对于 $[1,n]$ 整个区间的最小值 $A_p$，所有包含这个最小值的区间都合法，那么 $B_p=p\times (r-p+1)$。类似地推广到到任意区间 $[l,r]$，其最小值 $A_p$ 满足 $B_p=(p-l+1)\times(r-p+1)$。

接下来考虑如何构造。

根据上面的思路，先找到整个序列一个合法的最小值，然后以这个最小值为分界点，左右两侧两个区间递归计算。由于每次找到的是该区间内最小值，因此根据递归层数赋值，第 $i$ 层的最小值赋 $i$ 即可满足题意。

但是原序列不一定是排列，也就是说区间中有多个值满足题意。那么我们选择一个进入递归后，如果下一层出现一个点使得 $B_p>(p-l+1)\times(r-p+1)$，那么它即使是这个区间的最小值，也无法达到 $B_p$ 个。因此它一定是上一层的最小值，对其赋上一层的值即可。

:::info[实现与时间复杂度]{open} 您可以参考下方代码理解。考虑类似启发式合并的思想，从两端使用两个指针分别从 $l,r$ 向中间处理，每次都判断左侧和右侧是否有上述两种情况的任意一种。如果 $p$ 满足情况并确定值，则递归进入 $[l,p-1]$ 和 $[p+1,r]$ 继续处理，问题规模减小 $1$。假设区间总长度 $m$，从一侧扫描了 $k$ 个点才找到合法位置，那么能在更近的一边找到答案，扫描花费的次数为 $\min(k,m-k)$，并分割出了 $k$ 和 $m-k+1$ 两个区间，可以得出递推式：

因此类似于启发式合并，递归最多 $O(\log n)$ 层，时间复杂度为 $O(n \log n)$。但是不一定跑满。

::::success[AC 代码]

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 10;
int n;
long long a[maxn], b[maxn];
void solve(int l, int r, int cnt)
{
    if (l > r)
        return;
    int s = l, t = r;
    while (s <= t)
    {
        long long x = 1ll * (s - l + 1) * (r - s + 1);
        if (x == b[s])
        {
            a[s] = cnt;
            solve(l, s - 1, cnt + 1);
            solve(s + 1, r, cnt + 1);
            return;
        }
        if (x < b[s])
        {
            a[s] = cnt - 1;
            solve(l, s - 1, cnt);
            solve(s + 1, r, cnt);
            return;
        }
        s++;
        x = 1ll * (t - l + 1) * (r - t + 1);
        if (x == b[t])
        {
            a[t] = cnt;
            solve(l, t - 1, cnt + 1);
            solve(t + 1, r, cnt + 1);
            return;
        }
        if (x < b[t])
        {
            a[t] = cnt - 1;
            solve(l, t - 1, cnt);
            solve(t + 1, r, cnt);
            return;
        }
        t--;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    solve(1, n, 1);
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    return 0;
}

::::