#include using namespace std; namespace BIT_{ typedef int BITTYPE; #define BIT_SIZE 10000 #define MAX_CNT 100 //int cnt=0; //BITTYPE mems[MAX_CNT][BIT_SIZE]; BITTYPE mem[BIT_SIZE]; }; //[1,n],0は扱えない! template class BIT{ private: T* bit;int n; public: BIT(int _n){bit=BIT_::mem;fill(bit,bit+BIT_SIZE,0);n=_n;} BIT(T* _table,int _sz,int _n){bit=_table;fill(bit,bit+_sz,0);n=_n;} int sum(int i){int s=0;while(i>0){s+=bit[i];i-=i&-i;}return s;} int sum(int lb,int ub){return sum(ub)-sum(lb-1);} void add(int i,int x){while(i<=n){bit[i]+=x;i+=i&-i;}} //v[1]+v[2]+...+v[x]>=wとなる最小のxを求める int lowerbound(int w){if(w<=0)return 0;int x=0;for(int k = (1<<(31-__builtin_clz(n))); k >0 ; k>>=1)if(x+k<=n&&bit[x+k]> N >> K; assert(1 <= N && N <= 1000); assert(1 <= K && K <= 1000); vector> a(K); for(auto& it : a)it.reserve(N); { map z; for(int i = 0; i < N; i++){ int in; cin >> in; a[i % K].push_back(in); z[in] = 0; } //座圧 { int cnt = 1; for(auto& it : z)it.second = cnt++; for(auto& it : a)for(auto& jt : it)jt = z[jt]; } } int res=0; for(auto& b : a){ BIT bit(N); for(auto& it : b){ res+= bit.sum(it + 1,N); bit.add(it,1); } sort(b.begin(),b.end()); } for(int i = 0; i < N - 1; i++) if(a[i % K][i / K] > a[(i + 1) % K][(i + 1) / K]) res = -1; cout << res << endl; return 0; }