Cerința

Se citește un număr natural impar n (n<10). Afișați în ordine lexicografică toate permutările mulțimii {1,2,…,n} în care n se află în mijlocul permutării.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran permutările cerute, câte una pe fiecare rând și având elementele separate prin câte un spaţiu.

Restricții și precizări

• 1 ≤ n < 10

Exemplu:

Intrare

3

Ieșire

1 3 2  
2 3 1 

Explicație

S-au generat permutările în care 3 se află pe poziția a doua (în mijlocul permutării).