O subsecvenţă a[i], a[i+1], ..., a[j] se numeşte zig-zag dacă a[i] > a[i+1] < a[i+2] > … sau a[i] < a[i+1] > a[i+2] < … . O secvenţă aproape-zig-zag de ordin K  este o secvenţă care conţine cel mult K greşeli. O greşeală se defineşte ca fiind un triplet format din elemente cu indici consecutivi ale secvenţei care nu este zig-zag.

Să se găsească toate subsecvenţele aproape zig-zag de ordin K de lungime mai mare sau egală cu 3.
 

h2. Date de intrare
Fişierul de intrare zigzag.in conţine pe prima linie două numere întregi N şi K cu semnificaţia din enunţ. Următoarea linie conţine N numere întregi care reprezintă elementele vectorului a.

h2. Exemplu

table(example). |_. salturi.in |_. salturi.out |

table(example). |_. zigzag2.in |_. zigzag2.out |

| 4 1
2 1 1 2
| 2