题目描述

在我国传统文化中，数字“八”象征着吉祥与好运，因此这个数字在许多场合中都受到特别的重视。阿兔深受这一文化影响，非常喜爱数字“八”，因此他常常将“八”字融入到队名中，比如“兔八鸽”、“机电八队”等。

数组中数字“八”在也具有特殊意义。具体来说，如果一个区间 $[l,r]$ 内恰好包含了八个互不相同的数字，那么我们称这个区间为一个“吉祥区间”。

阿兔非常喜爱“吉祥区间”，他想知道，对于某个给定的区间 $[l,r]$，最多能够划分出多少个互不相交的子区间，满足“吉祥区间”的条件。

输入格式

第一行包含一个正整数 $n,q \ (1\leq n,q \leq 2*10^{5})$，表示数组长度和操作的总次数。

第二行包含 $n$ 个整数 $a_{i} \ (|a_{i}| \leq10^{9})$，表示数组的每个数字。

接下来 $q$ 行，每行表示一次查询操作，则包含两个正整数 $l,r \ (1\leq l \leq r \leq n)$，表示查询的区间。

输出格式

对于每次查询操作，输出一个整数，表示在给定区间 $[l,r]$ 内，最多能够划分出多少个互不相交的子区间，满足“吉祥区间”的条件。

18 8
1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1 88 88
1 7
1 8
2 9
2 15
2 16
2 17
1 16
2 18

0
1
0
0
1
1
2
1

解释 #1

对于第三组查询，给定的区间 $[2,9]$ 最多只能包含 $7$ 个互不相同的数字，因此无法满足“吉祥区间”条件。

对于第七组询问，给定的区间可以划分为两个互不相交的子区间： $[1,8]$ 和 $[9,16]$，各包含八个互不相同的数字。每个子区间都恰好包含 $8$ 个互不相同的数字，因此能够满足“吉祥区间”条件。