// あの花はまだどこかに咲いているに違いない // 我们会慢慢长大成人,在不断流逝的季节之中,盛开在路旁的花儿们,也在渐渐变化,盛开在那个季节里的花朵叫什么名字呢,在风中小小摇曳,伸手触碰便被扎得疼痛,把脸凑近,就能闻到一股淡淡的青涩的太阳芳香,那股芳香渐渐消散,而我们渐渐长大,但是,那朵花一定依旧盛开在某处。 // Code by ttq012. #include #define eb emplace_back #define int long long using namespace std; const int N = 500100; const int ready = 1e9 + 7; const int base = 256; const int inf = 0x0d000721ll << 2 | 0xAC66666; namespace ttq012 { int read() { int o = 1, x = 0; char ch; while (!isdigit(ch = getchar())) { if (ch == '-') { o = -o; } } x = ch & 15; while (isdigit(ch = getchar())) { x = (x << 3) + (x << 1) + (ch & 15); } return x * o; } int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1, y = 0; return a; } int g, xp, yp; g = exgcd(b, a % b, xp, yp); x = yp, y = xp - yp * (a / b); return g; } int ksm(int a, int b, int c) { a %= c; int ans = 1; while (b) { if (b & 1) { ans = ans * a % c; } a = a * a % c; b >>= 1; } return ans; } int Inv(int a, int ready) { return ksm(a, ready - 2, ready); } // calc a^(b^c) int calcpow(int a, int b, int c) { int k = ksm(b, c, ready - 1); if (k >= ready - 1) { k = k % (ready - 1) + (ready - 1); } return ksm(a, k, ready); } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int lcm(int a, int b) { return a / gcd(a, b) * b; } void swap(int &a, int &b) { a ^= b ^= a ^= b; } } // using namespace ttq012; namespace ttq012 { struct myhash{ static uint64_t rand(uint64_t x){ x^=x<<13; x^=x>>7; return x^=x<<17; } size_t operator()(size_t x)const{ static const uint64_t f_rand=chrono::steady_clock::now().time_since_epoch().count(); return rand(x+f_rand); } }; int a[N], vis[N], z[N]; void add(int x, int v) { for (; x < N; x += (x &- x)) { z[x] += v; } } int query(int x) { int s = 0; for (; x; x -= (x &- x)) { s += z[x]; } return s; } int f[N], b[N]; void run() { int n = read(), k = read(), all = 0; for (int i = 1; i <= n; ++i) { a[i] = read(); b[i] = a[i]; } sort(b + 1, b + n + 1); for (int i = 1; i <= k; ++i) { vector v, w; for (int j = i; j <= n; j += k) { v.eb(a[j]); w.eb(b[j]); } vector ww = v; sort(ww.begin(), ww.end()); sort(w.begin(), w.end()); if (w != ww) { cout << "-1\n"; return; } } set> se; map mp, box; for (int i = 1; i <= n; ++i) { ++box[a[i]]; } for (int i = 1; i <= n; ++i) { se.insert({a[i], box[a[i]]}); } int idx = 1; for (auto &x : se) { mp[x.first] = idx; ++idx; } for (int i = 1; i <= n; ++i) { a[i] = mp[a[i]]; } for (int i = 1; i <= k; ++i) { vector v, w; for (int j = i; j <= n; j += k) { v.eb(a[j]); } for (auto &j : v) { all += query(N - 1) - query(j); add(j, 1); } for (auto &j : v) { add(j, -1); } } cout << all << '\n'; } } signed main() { ttq012::run(); return 0; } /* */