牛逼题，贺的强大 \(O((n+q) \sqrt{n})\) 做法（。
很有根号智慧 /hs /bx
先把 \(b_i \leftarrow i-1-b_i\)，也就是变成 \(j \lt i \land a_j \lt a_i\) 的个数。
首先限制肯定是后面的优先级更高，于是有以下两种求出排列的方法：
- \(\textbf{Method } 1\)：正序枚举 \(i = 1 \sim n\)，因为需要优先满足后面的限制，所以贪心地令 \(a_i = b_i+1\)，然后把 \(j \in [1,i-1]\) 的所有 \(a_j \ge a_i\) 都 \(+1\)（让位）。这个直接做可以 \(O(n)\) 地求出 \(a_i\)。
- \(\textbf{Method } 2\)：倒序枚举 \(i = n \sim 1\)，这时只要满足后缀限制即可填最终答案，考虑维护一个取值集合 \(S\)（初始为 \([1,n]\)），每次在 \(a_i\) 填入 \((b_i+1)\text{ -th max}(S)\)。这个直接做是 \(O(n^2)\) 的，但可以求出 \(a_{1 \sim n}\) 的所有值。
观察法二到底在干什么，其实就是把后面可能的贡献放到一起再由被转移者自行取出会转移到它的贡献（，那么这两种方法事实上就是在做同一件事情，于是可以把它们缝起来交叉使用，正确性没有问题。
考虑这两种方法各自的特征：法一比较适合暴力（？，法二则可以轻易地（？）预处理、合并前后两段区间的答案（合并 \(A,B\) 时，\(A\) 的每个值会保持相对顺序变为 \(B\) 中选剩下的值，这是可以双指针的），那么就可以分块，对散块应用法一，对整块预处理从 \(R_i\) 扫到 \(L_i\) 后 已经选走的 每个值以及对应的位置（按值升序放在 vector 里）（考虑如何预处理：我们直接扫 \(i = R \sim L\)，每次暴力地归并 \((b_i + 1, i)\) 和后面的集合，这样做总复杂度是 \(O(B^2 \dfrac{n}{B}) = O(nB)\)）。考虑某一块每两次修改之间的所有询问，将它们挂在这一块上和维护的已取值集合一起归并，每个询问只会被挂到 \(O(\dfrac{n}{B})\) 个块上，每次归并每个询问会贡献 \(O(1)\)，那么复杂度就是 \(O((n+q) \dfrac{n}{B})\) 的。注意这里我们还需要对每一块上挂的询问按值升序排序，考虑修改是单点修改，那么所有块 “每两次修改” 的个数总和就是 \(O(q)\)，于是我们可以以 \(B\) 为底使用 \(O(B + |S|)\) 的基数排序，这里的 \(\sum |S| = q\)，复杂度是 \(O(q (\dfrac{n}{B} + B))\)。
然后考虑每次修改怎么维护这一块的已取值集合，由于我们有一个双指针做到 \(O(|A| + |B|)\) 的合并方法，所以你可以暴力地把要修改的元素从 vector 里分离出来，改完再合并分出来的三段，复杂度还是 \(O(q B)\)。
所以总复杂度就是 \(O((n + q) (\dfrac{n}{B} + B))\)，块长直接取 \(O(\sqrt{n})\) 就可以 \(O((n+q) \sqrt{n})\) 了。
由于要挂询问，不妨离线对每个块分别处理（块间的贡献不是立即要求的）。
注意下标不要搞混了 /yun，以及对于询问需要从 \(x+1\) 开始转移，所以提前 ++x 就好了。
// head and IO
#define ep emplace_back
#define all(x) begin(x),end(x)
using ll = long long; using vi = vector<int>;
struct Info { int v, x; Info(int v=0,int x=0) : v(v), x(x) {} }; using Set = vector<Info>;
constexpr int N = 100003, B = 323;
int n, q, b[N], c[N]; Set now, s1, s2, s3;
struct qry { int op, x, v; } qr[N]; vi Q;
inline void Mer(Set a, Set b, Set &fin){
fin.clear(); int p1 = 0, p2 = 0;
int n1 = a.size(), n2 = b.size();
for(; p1 < n1; fin.ep(a[p1].v+p2,a[p1].x), ++p1)
for(; p2 < n2 && a[p1].v+p2 >= b[p2].v; fin.ep(b[p2]), ++p2);
for(; p2 < n2; fin.ep(b[p2]), ++p2); // O(|A| + |B|)
}
inline void Spl(Set a, int x, Set &l, Set &r){
l.clear(), r.clear(); int n1 = a.size();
for(int i = 0; i < n1; ++i)
if(a[i].x > x) r.ep(a[i]);
else l.ep(a[i].v-r.size(),a[i].x); // 这里因为集合内部有序 所以之前放到右侧集合的都会对它产生 +1 的贡献
}
inline void Sort(vi &vec){
static vi buc1[B], buc2[B];
for(int x : vec) buc1[qr[x].v%B].ep(x); vec.clear();
for(int i = 0; i < B; ++i)
for(int x : buc1[i]) buc2[qr[x].v/B].ep(x);
for(int i = 0; i < B; ++i)
for(int x : buc2[i]) vec.ep(x);
for(int i = 0; i < B; ++i) buc1[i].clear(), buc2[i].clear(); // O(B + |S|)
}
inline void Sol(){
if(!Q.size()) return; Sort(Q), s3.clear();
//printf("before solving : ");
//for(int x : Q) printf("(%d , %d) ",qr[x].x,qr[x].v); puts("");
for(int x : Q) s3.ep(qr[x].v,-x); // < -qr[x].x >
Mer(s3, now, s3), Q.clear();
for(auto t : s3) if(t.x < 0) qr[-t.x].v = t.v;
}
inline void Mdf(int x, int d){
Spl(now, x, s1, s2), Spl(s1, x-1, s1, s3);
s3[0].v += d-b[x], b[x] = d;
Mer(s1, s3, s1), Mer(s1, s2, now);
}
main(){
rd(n); for(int i = 1; i <= n; ++i) rd(b[i]), c[i] = b[i] = i-1-b[i];
rd(q); for(int i = 1; i <= q; ++i){
rd(qr[i].op), rd(qr[i].x);
if(qr[i].op == 2) qr[i].v = b[qr[i].x]+1, ++qr[i].x;
else rd(qr[i].v), b[qr[i].x] = qr[i].v = qr[i].x-1-qr[i].v;
}
for(int i = 1; i <= n; ++i) b[i] = c[i];
const int Max = (n-1)/B+1;
for(int id = 1; id <= Max; ++id){
const int L = (id-1)*B+1, R = min(id*B,n);
now.clear(); for(int i = R; i >= L; --i) Mer(Set{Info(b[i]+1,i)},now,now); // O(B^2 \times n/B)
//for(auto t : now) printf("(%d , %d) ",t.x,t.v); puts("");
for(int i = 1; i <= q; ++i)
if(qr[i].op == 1){
if(qr[i].x >= L && qr[i].x <= R)
Sol(), Mdf(qr[i].x, qr[i].v);
} else {
if(qr[i].x <= R){
if(qr[i].x <= L) Q.ep(i);
else for(int j = qr[i].x; j <= R; ++j) qr[i].v += b[j]+1 <= qr[i].v;
}
}
Sol(); // 处理最后没有修改的询问
}
for(int i = 1; i <= q; ++i)
if(qr[i].op == 2) writeln(qr[i].v);
}
// mobai。