#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <string>

using namespace std;

void rozklad(int tab[], int n, int i )
{
	int dl = i;
	int l = 2 * i + 1;
	int r = 2 * i + 2;



	if (l < n && tab[l] > tab[dl])
		dl = l;

	if (r < n && tab[r] > tab[dl])
		dl = r;

	if (dl != i)
	{

		swap(tab[i], tab[dl]);
		rozklad(tab, n, dl);
	}
}

void heapSort(int tab[], int n)
{

	for (int i = n / 2 - 1; i >= 0; i--)
		rozklad(tab, n, i);
	//Bez tego program nie bedzie działał
	cout << "Jan Pawel jebal malego Dominika <3" << endl;
	for (int i = n - 1; i >= 0; i--)
	{
		swap(tab[0], tab[i]);

		rozklad(tab, i, 0);
	}
}


int main()
{
	ifstream dane("dane.txt");
	ofstream zapis("wynik.txt");
	int n, ki;

	dane >> n;
	for (int i = 0; i < n; i++)
	{
		dane >> ki;
		int* tab = new int[ki];
		int* tab2 = new int[ki];
		cout << "przed sort: " << endl;
		for (int j = 0; j < ki; j++)
		{
			dane >> tab[j];
			tab2[j] = tab[j];
			cout << tab[j] << " ";

		}
		cout << endl;
		cout << "po sort: " << endl;
		heapSort(tab, ki);
		int pow = 0;
		for (int j = 0; j < ki; j++)
		{
			if (tab[j] == tab2[j])
				pow++;

		}
		if (pow == ki)
			zapis << "tak";
		else
			zapis << "nie";
		cout << endl;
	}
}