using System; using System.Collections.Generic; using System.Collections; using System.Collections.Specialized; using System.Linq; using System.Text; using System.IO; using System.Reflection; using static System.Math; using System.Numerics; //using nint=System.Int32; static class Program{ const int mod=(int)1e9+7; const double eps=1e-11; static void Main(){ Sc sc=new Sc(); var s=sc.Ia; var a=sc.Arr(s[0],()=>sc.I); var wm=new Wm(a); long ans=0; for(int i = 0;i>1); } } public class Wm{ private int[][] ra; private int[] za; private const int b=30; private int n; public Wm(int[] a){ n=a.Length; var d=new int[b+1][]; ra=new int[b+1][]; for(int i = 0;i<=b;i++) { d[i]=new int[n]; ra[i]=new int[n+1]; } var d0=new int[2][]{new int[n],new int[n]}; var d1=new int[2][]{new int[n],new int[n]}; var h0=new int[]{0,0}; var h1=new int[]{0,0}; za=new int[b+1]; for(int i = 0;i=0;i--) { if(((k>>i)&1)==1){ r=ra[i][r+1]+za[i]-1; l=ra[i][l+1]+za[i]-1; } else{ r=r-ra[i][r+1]; l=l-ra[i][l+1]; } } return r-l; } public int Rl(int l,int r,long k){ l--; int p=0; for(int i = b;i>=0;i--) { if(((k>>i)&1)==1){ p+=r-l; r=ra[i][r+1]+za[i]-1; l=ra[i][l+1]+za[i]-1; p-=r-l; } else{ r=r-ra[i][r+1]; l=l-ra[i][l+1]; } } return p; } public int Rm(int l,int r,long k){ l--; int p=0; for(int i = b;i>=0;i--) { if(((k>>i)&1)==1){ r=ra[i][r+1]+za[i]-1; l=ra[i][l+1]+za[i]-1; } else{ p+=r-l; r=r-ra[i][r+1]; l=l-ra[i][l+1]; p-=r-l; } } return p; } public int Qt(int l,int r,int k){ l--; int p=0; for(int i = b;i>=0;i--) { if((r-ra[i][r+1])-(l-ra[i][l+1])(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i