幽默数

容易发现，在左端点固定的时候，若右端点向右移动，则区间的 $\text{lcm}$ 值要么不变，要么至少乘以 $2$。而对于一个质数，它不可能成为任意两个与它不等的数的 $\text{lcm}$，而第 $3 \times 10^5 + 1$ 个质数是 $4256233$，所以在所有区间的 $\text{lcm}$ 中，那些大于 $4256233$ 的是没有用的。

因此，记 $V = 4256233$，则当左端点固定的时候，不同的有用 $\text{lcm}$ 只有 $\log V$ 个。

考虑从右向左移动左端点，并且维护以当前点为左端点的不同 $\text{lcm}$。具体地，可以用两个集合 $A, B$ 分别维护当前存在的不同 $\text{lcm}$ 和所有可能有用的 $\text{lcm}$。左端点左移到 $i$ 的时候，需要将 $a_i$ 放入 $A$，并遍历 $A$ 中本来就存在的区间，对 $a_i$ 取 $\text{lcm}$ 后重新放入 $A$。每次更新完之后，就把当前 $A$ 中的元素放入 $B$ 中。最后对 $B$ 中的元素求 $\text{mex}$ 即可。

时间复杂度 $O(n \log^2 V)$。