A96172.皓仔的宝石项链

皓仔得到了 $n$ 个有着自己颜色的宝石，每个宝石的颜色都使用一个数字来记录， 他希望可以使用这些宝石来拼装一个项链。

皓仔决定在其中选择一段区间 $[L, R]$， 并且将其中所有的宝石取出来拼装项链。

皓仔希望这一条项链的颜色是各自不同的， 因此对于颜色重复的宝石他只会使用其中一颗。

现在皓仔有 $m$ 种区间的选择方案， 请你告诉他每一种方案可以得到的项链最大长度是多少？

第一行给定两个数字 $n, m$， 代表宝石的总数量和皓仔的选择方案数。

第二行给出 $n$ 个数字 $a_1, a_2, ..., a_n$， 代表每一个宝石的颜色 。

接下来 $m$ 行每行给出两个数字 $L_i, R_i$， 代表第 $i$ 个方案选择的区间范围。

输出 $m$ 行， 输出每一种方案可以得到的项链最大长度。

【数据范围】

对于所有测试数据保证： $1 \le n, m \le 5000$，$1 \le a_i \le 10^9$，$1 \le L \le R \le n$。