zigsort

Zigsort

h2. Restricţii

* N ≤ 100000

* 1≤ N ≤ 100000

* 1 ≤ K ≤ 4 ≤ N

* Daca K > 1 atunci N % K = 1 (toate secventele necrescatoare / nedescrescatoare au lungime K).

* 1 ≤ A[i] ≤ 100000 pentru orice i
* Daca K > 1 atunci N % K = 1 (toate secventele monotone au lungime K).

* Programul va fi punctat doar daca pentru orice test *M* *≤* *375000* iar interschimbarile sunt valide (pozitiile *i* sunt din intervalul *[1, N-1]*, si aplicate in ordinea in care au fost afisate sorteaza vectorul conform restrictiilor).

* In fisierul de intrate vor fi maxim 10 teste.

* In fisierul de intrare vor fi maxim 20 teste.

h2. Exemplu

  4 1
  5 6 3 1
  7 3

  6 7 5 3 2 1 9 10

  6 7 5 3 2 1 9

| 2 1 2
  4 1 4 5 4
|

Pentru primul test reprezentam interschimbarile:
1 2 3 4

5 6 3 1 -> A[] initial, la final trebuie ca @A[1]@ ≥ @A[2]@ ≤ @A[3]@ ≥ @A[4]@

5 6 3 1 -> A[] initial, la final trebuie ca @A[1]@ > @A[2]@ < @A[3]@ > @A[4]@

        aplicam swap(1,2) =>
6 5 3 1
        aplicam swap(2,3) =>

9721