/*
 *	31-1-3: Řazení kořenek
 *
 *	Martin Medvěd Mareš, říjen 2018
 *
 *	U každé části řešení (hledání NRP / hledání pohybů) si můžete
 *	vybrat, jestli se použije pomalý (kvadratické) nebo rychlý (N*log N)
 *	algoritmus.
 */

#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

/*** Nastavítka ***/

#define MAXN 1000
#define SLOW_NRP	// Použít pomalý algoritmus na NRP
#define SLOW_MOVES	// Použít pomalý algoritmus na nalezení pohybů

/*** Základní datové struktury ***/

// Vstup
int X[MAXN+1];		// Pozor, prvky číslujeme od 1
			// X[0] je vždy -∞
int n;

// Nejdelší rostoucí posloupnost
int nrp[MAXN];		// Indexy prvků ležících v NRP
int n_nrp;
int in_nrp[MAXN+1];	// in_nrp[x] = 1 <=> x je v NRP

// Výstup: seznam pohybů
int move_x[MAXN];	// Které prvky posouvat
int move_by[MAXN];	// O kolik doprava posouvat
int n_moves;

/*** Pomalý algoritmus na NRP ***/

#ifdef SLOW_NRP

int D[MAXN+1];	// D[i] = délka NRP končící i-tým prvkem
int B[MAXN+1];	// B[i] = předchůdce prvku i v NRP

void find_nrp(void)
{
	// Dynamické programování
	for (int k=1; k<=n; k++) {
		D[k] = 1;
		B[k] = 0;
		for (int i=1; i<k; i++)
			if (X[i] < X[k] && D[i] + 1 > D[k]) {
				D[k] = D[i] + 1;
				B[k] = i;
			}
	}

	// Nalezení konce nejdelší posloupnosti
	int end = 1;
	for (int k=1; k<=n; k++)
		if (D[k] > D[end])
			end = k;

	// Rekonstrukce NRP pozpátku
	n_nrp = D[end];
	int pos = n_nrp;
	while (end) {
		in_nrp[X[end]] = 1;
		nrp[--pos] = end;
		end = B[end];
	}
}

/*** Rychlý algoritmus na NRP ***/

#else

int P[MAXN+1];	// X[P[i]] = nejmenší možný konec NRP délky i
int B[MAXN+1];	// X[B[i]] = předchůdce prvku X[i]

void find_nrp(void)
{
	X[0] = INT_MIN;
	P[0] = 0;
	int nP = 1;	// Počet hodnot v poli P menších než +∞

	for (int k=1; k<=n; k++) {
		// Binární vyhledávání
		int l = 0, p = nP;
		while (l < p-1) {
			// Invariant: X[P[l]] < X[k] <= X[P[r]]
			int m = (l+p) / 2;
			if (X[P[m]] >= X[k])
				p = m;
			else
				l = m;
		}

		// Přepsání hodnoty na nalezené pozici
		P[p] = k;
		B[k] = P[l];
		if (p >= nP)
			nP++;
	}

	// Rekonstrukce NRP pozpátku
	n_nrp = nP - 1;
	int pos = n_nrp;
	int end = P[pos];
	while (end) {
		in_nrp[X[end]] = 1;
		nrp[--pos] = end;
		end = B[end];
	}
}

#endif

/*** Pomalý algoritmus na hledání pohybů ***/

#ifdef SLOW_MOVES

int Xcopy[MAXN+1];	// Kopie vstupu, ve které simulujeme pohyby

void find_moves(void)
{
	for (int i=1; i<=n; i++)
		Xcopy[i] = X[i];

	int next = 1;	// Následující pozice, na kterou chceme přesouvat
	for (int x=1; x<=n; x++) {
		// Nalezneme, kde leží prvek x
		int ix = 0;
		for (int i=1; i<=n; i++)
			if (Xcopy[i] == x)
				ix = i;
		// printf("found %d at %d: ", x, ix);

		if (in_nrp[x]) {
			// Je v NRP => nepřesouváme
			// printf("in NRP\n");
			next = ix + 1;
		} else {
			if (next > ix)	// +/- 1: Přesun z pozice ix na ix+1 nic nestojí
				next--;
			// printf("move %d[%d] by %d\n", ix, Xcopy[ix], next-ix);
			move_x[n_moves] = x;
			move_by[n_moves] = next - ix;
			n_moves++;

			// Odsimulujeme přesun, aby Xcopy bylo stále aktuální
			if (next < ix) {
				for (int i=ix; i>next; i--)
					Xcopy[i] = Xcopy[i-1];
			} else {
				for (int i=ix; i<next; i++)
					Xcopy[i] = Xcopy[i+1];
			}
			Xcopy[next++] = x;
		}
	}
}

#else

/*** Rychlý algoritmus na hledání pohybů ***/

int tn;				// Velikost intervalových stromů (mocnina dvojky)
int LT[4*MAXN+1];		// Intervalové stromy pro levou a pravou část
int RT[4*MAXN+1];
int LI[MAXN+1], RI[MAXN+1];	// Na které pozici nalevo/napravo je momentálně daný prvek

// Nastaví i-tý prvek ve stromu T na hodnotu x
void it_set(int *T, int i, int x)
{
	i += tn;
	T[i] = x;
	while (i > 1) {
		T[i/2] = T[i] + T[i^1];
		i /= 2;
	}
}

// Zjistí hodnotu i-tého prvku ve stromu T
int it_get(int *T, int i)
{
	return T[tn+i];
}

// Posčítá prvky v intervalu [i,j) ve stromu T (trik podle kuchařky)
int it_sum(int *T, int i, int j)
{
	i += tn;
	j += tn;
	int s = 0;
	while (i < j) {
		if (i%2)
			s += T[i++];
		if (j%2)
			s += T[--j];
		i /= 2;
		j /= 2;
	}
	return s;
}

void find_moves(void)
{
	// Najdeme nejmenší dost velkou mocninu dvojky
	// (levá část může spotřebovat až 2n pozic, navíč číslujeme od 1, proto +1)
	tn = 1;
	while (tn < 2*n+1)
		tn = 2*tn;

	// Počáteční pozice: nalevo není nic, napravo všechno
	for (int i=1; i<=n; i++) {
		RI[X[i]] = i;
		it_set(RT, i, 1);
	}

	int li = 1;	// Kam zapisujeme do levé části
	int ri = 1;	// Odkud odebíráme z pravé části
	for (int x=1; x<=n; x++) {
		// Kde je prvek x?
		if (LI[x] > 0) {
			// Je to přebytečný prvek nalevo => šup s ním na konec levé části
			move_x[n_moves] = x;
			move_by[n_moves] = it_sum(LT, LI[x]+1, li);
			n_moves++;
			it_set(LT, LI[x], 0);
			it_set(LT, li, 1);
			LI[x] = li;
			li++;
		} else {
			// Je někde napravo
			assert(RI[x] > 0);
			if (in_nrp[x]) {
				// Leží v NRP => formálně ho přesuneme doleva a vše před ním také
				while (ri <= RI[x]) {
					if (it_get(RT, ri)) {
						it_set(LT, li, 1);
						it_set(RT, ri, 0);
						LI[X[ri]] = li;
						RI[X[ri]] = 0;
						li++;
					}
					ri++;
				}
			} else {
				// Neleží v NRP => přesuneme ho doopravdy
				move_x[n_moves] = x;
				move_by[n_moves] = -it_sum(RT, 0, RI[x]);
				n_moves++;
				it_set(LT, li, 1);
				it_set(RT, RI[x], 0);
				LI[x] = li;
				RI[x] = 0;
				li++;
			}
		}
	}
}

#endif

/*** Testování ***/

// Vygeneruje náhodný vstup
void generate(void)
{
	for (int i=1; i<=n; i++)
		X[i] = i;
	for (int i=1; i<=n; i++) {
		int j = i + rand() % (n-i+1);
		int t = X[i];
		X[i] = X[j];
		X[j] = t;
	}
}

// Vypíše vstup
void show_in(void)
{
	printf("Input[%d]:", n);
	for (int i=1; i<=n; i++)
		printf(" %d", X[i]);
	printf("\n");
}

// Vypíše NRP
void show_nrp(void)
{
	printf("NRP[%d]:", n_nrp);
	for (int i=0; i<n_nrp; i++)
		printf(" %d(%d)", nrp[i], X[nrp[i]]);
	printf("\n");
}

// Vypíše nalezené přesuny a odsimuluje je
void show_moves(void)
{
	printf("Moves[%d]:\n", n_moves);
	assert(n_moves == n - n_nrp);
	for (int i=0; i<n_moves; i++) {
		int ix = 0;
		for (int j=1; j<=n; j++)
			if (X[j] == move_x[i])
				ix = j;
		int next = ix + move_by[i];
		printf("\t%d from %d to %d\n", move_x[i], ix, next);
		if (next < ix) {
			for (int i=ix; i>next; i--)
				X[i] = X[i-1];
		} else {
			for (int i=ix; i<next; i++)
				X[i] = X[i+1];
		}
		X[next++] = move_x[i];
	}

	printf("Sorted[%d]:", n);
	for (int i=1; i<=n; i++) {
		printf(" %d", X[i]);
		assert(i == 1 || X[i] > X[i-1]);
	}
	printf("\n");
}

// Hlavní program
int main(void)
{
	srand(42);
	n = MAXN;
	generate();
	show_in();

	find_nrp();
	show_nrp();

	find_moves();
	show_moves();

	return 0;
}