T492107 猫猫贴贴（加强版）（数据暂缺）

cxm 近日看到别的老师在联盟校集训的模拟赛中~~搬运~~出了一道名叫“猫猫贴贴”的题，被同学们用各种神仙做法拿下了。他感到很不爽，于是出了一道加强版，想让同学们爆零。现在你作为参加了 cxm 组织的集训的~~大冤种~~IOI AKer，不得不直面这道逆天题目。

cxm 家里有 $n$ 只猫猫，每只猫猫脖子上都挂着一个初始号码牌，上面标着猫猫的编号：$1, 2, \dots, n$。 每天晚上 cxm 都会把猫猫们拉到他身边，排成一排在他身边睡觉。我们认为 cxm 给猫猫们准备了“睡位队列”，编号 $1, 2, 3, \dots$。 有些猫猫很自觉，自己就会到 cxm 身边排成一排睡觉，不需要 cxm 抓过来；有些猫猫很调皮，需要 cxm 一只一只地抓。 cxm 睡前要吸猫。cxm 希望每次吸的猫的号码牌上的号码都是连续的。例如，当猫猫的号码牌序列是 $[1, 3, 2, 4, 5]$ 时，cxm 可以吸 $[3, 2, 4, 5], [3, 2], [4, 5]$ 的猫猫，但不能吸 $[1, 3]$ ，因为它们号码牌上号码不是连续的。 可能是因为猫猫是夜行生物，也可能是因为 cxm 最近压缩了猫猫们的伙食费，……，总之，猫猫们想尽办法要整蛊 cxm。猫猫们非常聪明，它们会自己用爪子把自己号码牌上的号码划掉后重新改成新的，它们以为这样 cxm 一定会疲于将号码改回来。（只可惜它们低估了 cxm 对吸猫的强烈欲望。）cxm 可管不了那么多，他才懒得把号码改回来，于是他只看每只猫猫当前号码牌上的号码，根据当前猫猫脖子上号码牌的号码决定吸哪些猫。 在给你讲题意的过程中，cxm 终于按捺不住了！cxm 决定不只是等到猫猫全部到自己身边，而是在拉猫猫的过程中也要吸猫。 因为玩了 [进化-evolve](https://g8hh.github.io/evolve/)，cxm 也进化了。他通过新获得的跨维观测能力，提前知道了他和猫猫们今天晚上的行动。作为副作用，他每次只能吸一段“睡位”连续的猫猫。现在，作为不幸参加了 cxm 组织的集训的 oier，你需要告诉他，每次他想吸猫的时候，他有多少种吸猫方案。

第一行一个整数 $n\ (n\le 10^4)$。 接下来一行 $n$ 个整数 $a_i$，表示初始时自觉猫猫的号码牌上初始的号码 $a_i\ (a_i \le 10^9)$。 接下来一行一个整数 $q\ (q \le 10^5)$。 接下来 $q$ 行，每行首先输入一个整数 $opt$，表示当前时刻发生时间的种类： 1. $opt = 1$，接下来输入两个整数 $p, x$，表示“睡位队列”中第 $p$ 只猫猫将自己的号码改成了 $x$。 2. $opt = 2$，接下来输入一个整数 $x$，表示 cxm 将一只编号为 $x$ 的猫猫捉到了，并放在“睡位队列”末尾。 3. $opt = 3$，接下来输入两个整数 $l, r$，表示 cxm 问你，如果他现在想吸“睡位”在 $[l, r]$ 的猫猫，他有多少种吸猫方案。 令 $q$ 表示当前在 cxm 身边的猫猫数量，则保证任何时候，$1\le p, l, r \le q$。

对于每一次 $opt = 3$，输出一行一个整数，表示 cxm 吸“睡位” $[l, r]$ 的猫猫的方案数。