CF351D Jeff and Removing Periods

给定一个由 $n$ 个整数构成的序列 $a_1, a_2, \ldots, a_n$。Jeff 可以对序列 $a$ 进行以下操作： - 选择三个整数 $v$、$t$、$k$（满足 $1 \leq v, t \leq n$，$0 \leq k$，$v + tk \leq n$），使得 $a_v = a_{v+t} = a_{v+2t} = \cdots = a_{v+tk}$； - 从序列 $a$ 中移除 $a_v, a_{v+t}, \ldots, a_{v+tk}$ 这些元素，余下的元素重新编号为 $a_1, a_2, \ldots, a_{n-k-1}$； - 对剩余的 $a$ 元素随意重新排列。 一个序列 $a$ 的“美丽值”定义为：将 $a$ 中所有元素删除所需的最少操作数。 Jeff 写下了一个长度为 $m$ 的整数序列 $b_1, b_2, \ldots, b_m$。现在他有 $q$ 个问题，每个问题由两个整数 $l_i, r_i$ 描述。对于每个问题，需要计算子序列 $b_{l_i}, b_{l_i+1}, \ldots, b_{r_i}$ 的美丽值。你需要根据给定的 $b$ 序列和所有询问，帮助 Jeff 求出每个问题的答案。

第一行包含一个整数 $m$ $(1 \leq m \leq 10^5)$。 第二行包含 $m$ 个整数 $b_1, b_2, \ldots, b_m$ $(1 \leq b_i \leq 10^5)$。 第三行包含一个整数 $q$ $(1 \leq q \leq 10^5)$ —— 询问数量。 接下来的 $q$ 行，每行包含一对整数 $l_i, r_i$ $(1 \leq l_i \leq r_i \leq m)$ —— 第 $i$ 个询问的区间。

输出 $q$ 行，每行一个答案，按输入顺序对应每个询问的美丽值。

由 ChatGPT 5 翻译