/*

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.

Questa soluzione effettua troppi confronti sull'ultimo input. Un'altra
soluzione, basata sulla randomizzazione dell'input, e` contenuta in median2.c.

Innanzitutto fissiamo due elementi che saranno quelli di
riferimento. Dopodiche', tramite ricerca ternaria localizziamo per ciascuno
degli elementi rimanenti dove esso va posizionato. Quando abbiamo inserito
tutti gli elementi, prendiamo quello al centro.

C'e` un'ottimizzazione addizionale: dopo che abbiamo inserito meta` degli elementi,
quelli ai bordi della lista ordinata corrente non possono essere mediani, e
quindi li possiamo eliminare, riducendo il numero di confronti.  Quindi, alla
fine, in realta` rimarra` solo il mediano.

*/


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

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

#define MAXN 1500

int forza[MAXN];
FILE *F;
int N;
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]; /* Il vettore di dati ordinati che stiamo costruendo. */


/* Questa funzione localizza la posizione in cui va inserito x all'interno di
	ord[], sapendo che deve trovarsi tra s e d, oppure immediatamente a sinistra
	di s, oppure immediatamente a destra di d. */

int trova(int x, int s, int d) {

	int t, s3 = s+(d-s)/3, d3 = s+(2*(d-s)+1)/3;

	assert(s <= d);

	if (s == d) {
		if (s) s--; else d++;
	}

	if (d == s+1) {
		t = Med3(ord[s], ord[d], x);
		if (t == x) return d;
		else if (t == ord[s]) return s;
		else return d+1;
	}


	/* s3 e d3 sono approssimativamente a 1/3 e a 2/3 tra s e d. */

	t = Med3(ord[s3], ord[d3], x);

	if (t == x) {
		if (s3+1 == d3) return d3;
		return trova(x, s3+1, d3-1);
	}

	if (t == ord[s3]) {
		if (s == s3) return s;
		return trova(x, s, s3-1);
	}

	if (d3 == d) return d+1;
	return trova(x, d3+1, d);
} 


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

	i = Med3(1, 2, 3);

	ord[1] = i;

	/* Innanzitutto fissiamo due elementi di riferimento. */

	if (i == 1) { ord[0] = 2; ord[2] = 3; }
	else if (i == 2) { ord[0] = 1; ord[2] = 3; }
	else { ord[0] = 1; ord[2] = 2; }

	l = 3;
	for(i=4; i<=N; i++) {
		/* Se abbiamo inserito piu` di meta` elementi, possiamo cancellare i due ai
			bordi di ord[] ogni volta che facciamo un inserimento, dato che non
			possono in alcun caso essere mediani. */

		if (i > (N+1)/2+1) {
			memmove(&ord[0], &ord[1], sizeof *ord * l);
			l -= 2;
		}

		if (l == 1) break;

		/* Troviamo dove va posizionato l'i-esimo elemento e lo inseriamo al suo
			posto. */

		t = trova(i, 0, l-1);
		memmove(&ord[t+1], &ord[t], sizeof *ord * (l-t)); 
		ord[t] = i;
		l++;
	}
  
	Answer(ord[l/2]);

	return 0;
}