题目背景

来源：陈江伦 2018 候选队论文题

题目描述

给定一个长度为 $n$ 的字符串 $P$，有 $m$ 次询问，每次给定两个参数 $l$ , $r$，询问子串 $P[l,r]$ 所构成的后缀树的结点数。

如果你不了解后缀树，你也可以理解为对 $[l,r]$ 的反串建后缀自动机。

注意在本题中，后缀树的根节点不计入答案。

输入格式

本题中用数字来表示字符串，不同的数字代表不同的字符，相同的数字代表相同的字符，数字的范围在 $[0,n]$ 之间。

第一行两个正整数 $n$ 和 $m$，表示字符串长度和询问个数。 第二行 $n$ 个用空格隔开的非负整数，表示这个字符串。 接下来 $m$ 行，每行两个正整数 $l,r$，表示询问子串 $[l,r]$ 的后缀树的结点数。

输出格式

输出 $m$ 行，每行一个正整数表示答案。

7 2
2 1 3 1 3 1 4
1 7
4 5

10
2

提示

对于 $30\%$ 的数据：$n,m\le 3\times 10^3$；

对于 $100\%$ 的数据满足：$n\le 10^5$，$m\le 3\times 10^5$，字符串的每个数字 $\le n$。