线性做法。

假设 $n,q$ 同阶，或 $q=\mathcal O(n)$。

---

首先容易从每个点 $l$ 开始，处理出最远的 $r\left(l\right)$，使得 $\left[l,r\left(l\right)\right]$ 是一个无同子序列。这个双指针可以做到。

---

然后对于一个 $L,R$ 的询问，可以发现答案为：

$$\max_{L\leqslant i\leqslant R}\left\{\min\left(r\left(i\right),R\right)-i+1\right\} $$

注意到 $r\left(i\right)$ 是单调的，因此可以二分出 $\min$ 函数取到 $R$ 的第一个位置 $p$，则 $\left[p,R\right]$ 的贡献为 $R-p+1$。

对于 $\left[L,p-1\right]$，需要对 $r\left(i\right)-i+1$ 取最大值，这个东西是静态的，可以使用 ST 表处理。

总复杂度 $\mathcal O\left(n\log n\right)$。

---

考虑优化。

首先，考虑不对 $p$ 进行二分求解；在求 $r\left(x\right)$ 的同时，我们维护一个类似 $r^{-1}$ 的数组；但是 $r$ 不是单射，所以我们取 $r^{-1}(y)$ 是所有满足 $r(x)=y$ 中 $x$ 最小的一个。

现在可以直接从 $r^{-1}$ 中查到 $p$。

---

对于静态区间最大值，其实可以直接四毛子算法。

普通的四毛子是 $\mathcal O\left(n\log\log n\right)\sim\mathcal O\left(1\right)$ 的。

具体地，将序列分块，令块长为 $\mathcal O\left(\log n\right)$，取出每一块的最大值放到 ST 表上去，时间复杂度为 $\mathcal O\left(\dfrac{n}{\log n}\cdot\log\left(\dfrac{n}{\log n}\right)\right)=\mathcal O(n)$。

对于每一块，在块内建立 ST 表，每块的时间复杂度为 $\mathcal O\left(\log n\log\log n\right)$，因此总复杂度为 $\mathcal O\left(n\log\log n\right)$。

查询的复杂度为 $\mathcal O\left(1\right)$。

---

但是众所周知 $\pm1$ RMQ 有优化。具体来说，对于一个长为 $n$ 的序列，相邻两个数差的绝对值恰好为 $1$，则可以将整个序列变成一个 $n$ 位二进制数；相同二进制表示的序列，最大值所在位置相同。

对每个长度为 $\log_2 n$ 的块预处理出最大值的位置，这个可以 $O\left(n\right)$ 递推出来。

对于一般的序列，可以在 $\mathcal O\left(n\right)$ 的复杂度内建立笛卡尔树，将 RMQ 问题规约为树上 LCA 问题；树上 LCA 问题又可以通过求树的欧拉序 $\mathcal O\left(n\right)$ 规约为 $\pm 1$ RMQ 问题，从而使用四毛子算法解决。

现在，我们已经理论上做到了题目的线性求解，然而四毛子算法的常数太大，因此我们再介绍几种常数较小的方法。

下述方法不要求查询是可重复贡献的。

---

一种方法还是在数列上分块，令块长为 $B$。

对于整块，预处理 $\mathcal O\left(\dfrac{n}{B}\right)$ 个块两两间的最大值，时间复杂度为 $\mathcal O\left(\dfrac{n^{2}}{B^{2}}\right)$；

对于散块，预处理前缀最大值和后缀最大值，总的时间复杂度为 $\mathcal O\left(n\right)$。

对于跨块的查询，可以拆为散块后缀 + 整块 + 散块前缀的形式，查询复杂度 $\mathcal O\left(1\right)$。

对于块内查询，复杂度为 $\mathcal O\left(B\right)$，但是期望只有 $\mathcal O\left(\dfrac{B}{N}\right)$ 的概率出现这类查询，因此单次期望复杂度为 $\mathcal O\left(\dfrac{B^{2}}{n}\right)$。

令 $B=\mathcal O\left(\sqrt{n}\right)$，就做到了 $\mathcal O\left(n\right)\sim\mathcal O\left(1\right)$ 的区间查询，其中查询部分的复杂度是期望意义下的。

然而，由于出题人很难猜到块长 $B$ 的具体取值，因此未必可以将单次查询卡到最劣的 $\mathcal O\left(B\right)$。

---

对于上述做法的一个优化是在每一个块上递归应用该做法，由于最多递归 $\mathcal O\left(\log\log n\right)$ 层，故预处理复杂度是 $\mathcal O\left(n\log\log n\right)$ 的。

查询的复杂度是 $\mathcal O\left(\log\log n\right)$，但是可以转化为 LCA 做到 $\mathcal O\left(\log\log\log n\right)$（或者表述为二分合法高度），使用二进制优化可以做到 $\mathcal O\left(1\right)$。

具体来讲，只要保证每个块的大小均为 $2$ 的整数次幂，并且每层的块的大小相同，即可使用端点二进制表示的异或值 $L\oplus R$ 的最高位 $1$ 的位置（使用 __builtin_clz），直接确定询问将在哪一层处理。

---

还有一种做法类似 Tarjan (LCA) 算法。

• 建立带权并查集。
• 将询问离线，按右端点位置放到序列上。
• 从左到右遍历序列，对于位置 $r$：
  • 令 fa[i - 1] = fa[i]；
  • 枚举所有询问的右端点 $l$，对于每个询问：
    • 执行 find(l)；
    • 此时，val[l] 即为查询的答案。

我感觉序列上这玩意是均摊线性的，但是没见人提过。

可以把原序列看成是一个链表，并查集的 fa[] 数组看做链表的 nxt[] 数组，find 操作看作链表删除操作。

由于链表中每个点最多被删去一次，因此均摊复杂度应为 $\mathcal O(n)$。