/*

Median Strength (IOI 2000)
Copyright (C) 2000 Paolo Boldi and Sebastiano Vigna

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA




Il programma utilizza una copia interna della libreria su cui si basa
l'interazione. La funzione Answer() stampa il numero di chiamate a Med3() e dice
se il risultato passato e` giusto o sbagliato.

Innanzitutto fissiamo due elementi s e d che saranno quelli di
riferimento. Dopodiche', dividiamo gli elementi in tre gruppi: quelli a
sinistra di s, quelli a destra di d e quelli in mezzo. Contando i tre gruppi
siamo in grado di stabilire in quale gruppo si trova il mediano, e in che
posizione. A questo punto ripetiamo il procedimento con il nuovo gruppo.

Di per se' ci sono alcuni input che potrebbero generare un numero enorme di
chiamate a Med3(). Pero` questi input sono rari, e disposti in maniera molto
particolare. Quindi per prima cosa calcoliamo una permutazione casuale degli
input, ed e` a questa che applichiamo la procedura. La probabilita` che un
input generi un numero di chiamate a Med3() molto elevato e` in questo modo
molto bassa per *qualsiasi* input.

*/


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

#define min(a,b) ((a)<(b)?(a):(b))

#define MAXN 1500

int forza[MAXN];
FILE *F;
int N, si;
int chiamate;

int GetN(void) {
	int i;
	F = stdin;
	fscanf(F, "%d\n", &N);

	for(i=0; i<N; i++) fscanf(F, " %d", &forza[i]);
	return N;
}

int Med3(int x, int y, int z) {
	chiamate++;
	x--; y--; z--;
	if (forza[x] < forza[y] && forza[y] < forza[z] || forza[x] > forza[y] && forza[y] > forza[z]) return ++y;
	if (forza[z] < forza[x] && forza[x] < forza[y] || forza[z] > forza[x] && forza[x] > forza[y]) return ++x;
	return ++z;
}

void Answer(int n) {
	F = stdout;

	fprintf(F, "%d\n", chiamate);
	fprintf(F, "Il risultato e` %s\n", forza[n-1] == (N+1)/2 ? "corretto" : "errato");
}


int ord[MAXN], posfsi;

/* Questa funzione e` ricorsiva, e trova l'n-esimo elemento (secondo l'ordine
   dei naturali) di una lista di l interi puntata da p. Inizialmente viene
   chiamata per trovare l'elemento di posto N/2 nella lista di N elementi
   puntata da ord, ma mano a mano che divi*/


	int trova(int n, int *p, int l) {
		int i, t, s=0, d=1;

		if (l == 1) return p[0];

		if (l < N) {
			t = Med3(si, p[0], p[1]);
			if (p-ord > posfsi && t == p[1] || p-ord < posfsi && t == p[0]) {
				t = p[0];
				p[0] = p[1];
				p[1] = t;
			}
		}

		for(i=2; i<l; i++) {
			t = Med3(p[s], p[d], p[i]);

			if (t == p[i]) {
				memmove(&p[d+1], &p[d], sizeof *p * (i-d));
				p[d++] = t;
			}
			else if (t == p[s]) {
				t = p[i];
				memmove(&p[s+1], &p[s], sizeof *p * (i-s));
				p[s++] = t;
				d++;
			}
		}

		if (l == N) posfsi = s;

		if (n < s) return trova(n, p, s);
		if (n == s) return p[s];
		if (n > s && n < d) return trova(n-s-1, p+s+1, d-s-1);
		if (n == d) return p[d];
		return trova(n-d-1, p+d+1, l-d-1);
	} 


void swapint(int *a, int *b) { int t = *a; *a = *b; *b = t; }

int main(int argc, char *argv[]) {
	int i;
	GetN();

	srand(clock());
	for(i=0; i<N; i++) ord[i] = i+1;

	/* Permutiamo a caso gli elementi in ord */

	for(i=N-1; i>0; i--) 
		swapint(&ord[i], &ord[(int)((rand()/(1.0+RAND_MAX))*(i+1))]);

	si = ord[0];
	Answer(trova(N/2, ord, N));

	return 0;
}