Arte moderna#10529

Arte moderna

1 secondo

128 megabyte

Difficile

I critici d'arte di tutto il mondo hanno solo recentemente iniziato a riconoscere il genio creativo della grande pittrice tra le mucche — Picovso.

Picovso dipinge in un modo davvero insolito. Inizia con una tela pulita di dimensioni $n \times n$ n \times n, rappresentata come una griglia $n \times n$ n \times n riempita di zeri, dove zero indica una cella vuota della tela. Quindi dipinge sulla tela $n^{2}$ n^2 rettangoli, utilizzando ciascuno degli $n^{2}$ n^2 colori esattamente una volta. Per comodità, i colori sono numerati da $1$ a $n^{2}$ n^2.

Per esempio, prima potrebbe dipingere un rettangolo con il colore $2$ , ottenendo la seguente immagine intermedia:

Poi potrebbe dipingere un rettangolo con il colore $7$ :

Infine, potrebbe dipingere un piccolo rettangolo con il colore $3$ :

I lati di ogni rettangolo sono paralleli ai lati della tela. Un rettangolo può occupare l'intera tela oppure essere costituito da una sola cella. Ogni colore da $1$ a $n^{2}$ n^2 viene utilizzato esattamente una volta, tuttavia i colori successivi possono coprire completamente parti dei rettangoli disegnati precedentemente.

Dato lo stato finale della tela, determina quanti degli $n^{2}$ n^2 colori potrebbero essere stati utilizzati per il primissimo rettangolo disegnato.

Input

La prima riga contiene la dimensione della tela $n (1 \leq n \leq 1000)$ n~(1 \le n \le 1000). Le successive $n$ righe descrivono lo stato finale della tela. Ogni riga contiene $n$ numeri interi nell'intervallo da $0$ a $n^{2}$ n^2. È garantito che l'immagine ottenuta potesse essere creata nel modo descritto sopra — disegnando in sequenza rettangoli di colori diversi.

Output

Stampa il numero di colori che potrebbero essere stati utilizzati per il primo rettangolo disegnato.

Esempi

In questo esempio il colore $2$ potrebbe essere stato utilizzato per il primo rettangolo. Il colore $3$ , evidentemente, deve essere stato disegnato dopo il colore $7$ , e il colore $7$ — dopo il colore $2$ . Poiché non vediamo gli altri colori, si può concludere che anche ognuno di essi potrebbe essere stato il primo.

Esempio 1