$RT$，我的同学用了一个维护区间最大值最小值的线段树，每次询问如果最大值小于询问值直接返回 $0$，最小值大于询问值就返回区间长度，如果不满足这两种情况就继续往下递归。

这样单次询问的复杂度最坏是 $O(n)$ 的，只要两个相邻的数一个大于询问值一个小于询问值就能让他搜到单点区间，然而这样做居然可以通过此题，因此请求添加hack数据叉掉这个假做法。

以下为数据生成器。

#include<cstdio>
int main() 
{
	freopen("12.in","w",stdout);
	puts("1000000 3000");
	for(int i=1;i<=1e6;i++) printf("%d ",(i&1)+1);
	for(int i=1;i<=3e3;i++) puts("A 1 1000000 2");
}