#include <iostream>

using namespace std;

#define SIZE 20

int solutie[SIZE], n;

bool valid(int k)
{
	for (int i = 1; i < k; i++)
		if (solutie[i] == solutie[k])
			return false;

	if (k <= n / 2) {
		for (int i = 1; i < k; i++)
			if (solutie[i] > solutie[i + 1])
				return false;
	}
	else {
		for (int i = n / 2 + 1; i < k; i++)
			if (solutie[i] < solutie[i + 1])
				return false;
	}
		return true;

}

void afis()
{
	for (int i = 1; i <= n; i++)
		cout << solutie[i] << ' ';
	cout << endl;
}

void BKT(int k)
{
	for (int i = 1; i <= n; i++) {
		solutie[k] = i;
		if (valid(k)) {
			if (k == n)
				afis();
			else BKT(k + 1);
		}
	}
}


int main()
{
	cout << "Dati numarul de elemente : ";
	cin >> n;

	for (int i = 0; i < n; i++) {
		cout << "A[" << i << "] = ";
		cin >> solutie[i];
	}

	BKT(1);




	system("pause");
	return 1;
}