分析：

听说主席树和莫队可以做，前者不想写，后者我不会...

我们考虑将询问离线，按照左端点排序，之后先处理好从1开始选的答案，之后枚举从1到n，之后依次删除nxt[i]，添加nxt[nxt[i]]，之后当询问左端点等于i的时候，更新答案。

附上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 1000005int n,m,a[N],vis[N],nxt[N],sum[N];int find(int x){ int ret=0; for(int i=x;i;i-=i&-i)ret+=sum[i]; return ret;}void fix(int x,int c){ for(int i=x;i