== include(page="template/taskheader" task_id="zigsort") ==

Fie un vector de numere naturale *A[]* ce contine *N* elemente. O sortare in zig-zag de ordin *k* se defineste ca o reanranjare a elementelor astfel incat :

Fie un vector de numere naturale *A[]* ce contine *N* elemente *cu valori distincte*. O sortare in zig-zag de ordin *k* se defineste ca o rearanjare a elementelor astfel incat :

a{~1~} ≥ a{~2~} ≥ ... ≥ a{~k~} ≥ a{~k+1~}

a{~1~} > a{~2~} > ... > a{~k~} > a{~k+1~}

a{~k+1~} ≤ a{~k+2~} ≤ ... ≤ a{~2*k+1~}

a{~k+1~} < a{~k+2~} < ... < a{~2*k+1~}

a{~2*k+1~} ≥ a{~2*k+2~} ≥ ... ≥ a{~3*k+1~}

a{~2*k+1~} > a{~2*k+2~} > ... > a{~3*k+1~}

si asa mai departe, adica :

primele _*k + 1*_ elemente trebuie sa fie in ordine necrescatoare
elementele de la pozitiile _*k + 1*_ pana la _*2 * k + 1*_ trebuie sa fie in ordine nedescrescatoare
elementele de la pozitiile _*2 * k + 1*_ pana la _*3 * k + 1*_ trebuie sa fie in ordine necrescatoare

primele _*k + 1*_ elemente trebuie sa fie in ordine descrescatoare
elementele de la pozitiile _*k + 1*_ pana la _*2 * k + 1*_ trebuie sa fie in ordine crescatoare
elementele de la pozitiile _*2 * k + 1*_ pana la _*3 * k + 1*_ trebuie sa fie in ordine descrescatoare

In general elementele de la pozitiile _*p * k + 1*_ pana la _*(p + 1) * k + 1*_ trebuie sa fie in ordine necrescatoare daca _*p*_ este par si nedescrescatoare daca _*p*_ este impar.

Pentru a rezolva problema trebuie sa implementati o astfel de sortare dar care sa foloseasca interschibari doar de elemente care sunt pe pozitii consecutive (swap *A[i]* si *A[i+1]*).

Pentru a rezolva problema trebuie sa implementati o astfel de sortare dar care sa foloseasca interschimbari doar de elemente care sunt pe pozitii consecutive (swap *A[i]* si *A[i+1]*).

h2. Date de intrare