#include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair P; typedef pair PP; const ll MOD=998244353; const double PI=acos(-1); template struct binary_indexed_tree{ int N; vector bit; binary_indexed_tree(int n):N(n+1){ bit = vector(n+1,0); N=n; } void add(int x,Type a){ x++;//1から始めるための補正 //for(int i=x; i<=N; i+=(i&-i)) bit[i] = addition(bit[i],a); while(x<=N){ //bit[x] = addition(bit[x],a); bit[x] =bit[x]+a; x += x&-x; } } Type sum(int x){ x++;//1から始まることに注意 Type ret=0; //for(int i=x; i>0; i-=(i&-i)) ret = addition(ret,bit[i]); while(x>0){ ret = ret+bit[x]; x -= x&-x; } return ret; } //[l,r]の範囲 // rはN-1以下 Type get(int l,int r){ if(r>N) return 0;//配列の外へのアクセス if(l>r) return 0;//本来は l<=r となるのでおかしい if(l==0) return sum(r);//[0,r]//ここでoutなわけか else return (sum(r) - sum(l-1)); } }; int main(){ int N; ll M; cin>>N>>M; vector p(N); for(int i=0;i>p[i]; p[i]--; } binary_indexed_tree bit(N+1); ll cnt=0; for(int i=0;i