Los críticos alrededor del mundo únicamente recientemente han comenzado a reconocer el genio creativo detrás de la gran pintora bovina, Picavasa.

Picavacas pinta de una manera muy particular. Ella comienza con un lienzo blanco ~N \cdot N~ representado por una cuadricula ~N \cdot N~ de ceros, donde un cero indica una celda vacía del lienzo. Ella luego pinta ~N^2~ rectángulos en el lienzo, uno en cada uno de ~N^2~ colores (numerados convenientemente ~1...N^2~). Por ejemplo, ella podría comenzar pintando un rectángulo en color 2, dando este lienzo intermedio:

2 2 2 0 
2 2 2 0 
2 2 2 0 
0 0 0 0

Ella podría luego pintar un rectángulo en color 7:

2 2 2 0 
2 7 7 7 
2 7 7 7 
0 0 0 0

Y luego ella podría pintar un pequeño rectángulo en color 3:

2 2 3 0 
2 7 3 7 
2 7 7 7 
0 0 0 0

Cada rectángulo tiene lados paralelos a los lados del lienzo, y un rectángulo podría ser tan grande como todo el lienzo o tan pequeño como una sola celda. Cada color de ~1...N^2~ es usado exactamente una vez, a pesar de que colores posteriores podrían cubrir completamente alguno de los colores previos.

Dado el estado final del lienzo, por favor cuente cuántos de los ~N^2~ podrían haber sido posiblemente el primer color que fue pintado.

Entrada

La primera línea de la entrada contiene ~N~, el tamaño del lienzo ~(1 \leq N \leq 1000)~. Las siguientes ~N~ líneas describen la pintura final en el lienzo, cada uno conteniendo ~N~ enteros que están en el rango ~0...N^2~. Se garantiza que la entrada ha sido pintada como se ha descrito anteriormente, pitnando rectángulos sucesivos en colores diferentes.

Salida

Por favor dé como salida la cuenta del número de colores que podrían haber sido pintados primero.

Ejemplo de Entrada

4
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0

Ejemplo de Salida

14

En este ejemplo, el color 2 podría haber sido el primero en ser pintado. El color 3 claramente tenía que haber sido pintado después del color 7, y el color 7 claramente tenía que ser pintado después del color 2. Como no vemos los otros colores, deducimos que ellos también podrían haber sido pintados de primero.

USACO 2017 US Open Contest, Platinum Problem 1. Modern Art.