Generate All Permutations

Given an array of n distinct integers, your task is to generate all possible permutations of the array. The output must list the permutations in lexicographical order (i.e. sorted as if they were words in a dictionary).

The solution should read the input from standard input (stdin) and write the output to standard output (stdout). Each permutation should be printed on a separate line, with the elements separated by a single space.

inputFormat

The first line of input contains a single integer n, the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output all the permutations of the given array in lexicographical order. Each permutation must be printed on a separate line, with each number separated by a single space.

1
5

5