Esta noche, en tu cine favorito están dando la película Joker y todos los asientos están ocupados. En el cine hay ~N~ filas con ~N~ asientos cada una, formando un cuadrado \(N × N\). Denotamos con ~1,2,..., N~ los espectadores en la primera fila (de izquierda a derecha); con ~N + 1,..., 2\cdot N~ los espectadores en la segunda fila (de izquierda a derecha); y así sucesivamente hasta la última fila, cuyos espectadores se indican con ~N^2 - N + 1,..., N^2~.

Al final de la película, los espectadores salen del cine en un orden determinado: el i -ésimo espectador que abandona su asiento es el que se indica con el número ~P_i~. El espectador ~P_{i + 1}~ espera hasta que el espectador ~P_i~ haya abandonado el cine antes de dejar su asiento. Para salir del cine, un espectador debe moverse de un asiento a otro hasta que salga de la plaza de asientos (cualquier lado de la plaza es una salida válida). Un espectador puede moverse de un asiento a uno de sus 4 asientos adyacentes (misma fila o misma columna). Al salir del cine, puede ser que cierto espectador ~x~ pase por un asiento actualmente ocupado por el espectador ~y~; en ese caso, el espectador ~y~ odiará al espectador ~x~ para siempre. Cada espectador elige la forma que minimiza la cantidad de espectadores que lo odiarán para siempre.

Calcule la cantidad de pares de espectadores ~(x, y)~ tal que ~y~ odiará ~x~ para siempre.

Restricciones

• ~2 \le N \le 500~

• La secuencia ~P_1, P_2,..., P_{N^2}~ es una permutación de ~{1,2,..., N^2}~.

Entrada

La entrada se da desde entrada estándar en el formato

n
p1, p2, ..., pn^2

Salida

Si ans es el número de pares de visores descritos en la declaración, debe imprimir en salida estándar

ans

Puntuación

En al menos 55% de los casos se tiene que ~n \leq 100~.

Ejemplo de entrada 1:

3
1 3 7 9 5 4 8 6 2

Ejemplo de salida 1:

1

Antes del final de la película, los espectadores se organizan en el cine de la siguiente manera:

1 2 3
4 5 6
7 8 9

Los primeros cuatro espectadores que abandonan el cine ~(1, 3, 7, 9)~ pueden salir del cine sin pasar por ningún asiento, para que nadie los odie.

Entonces, espectador ~5~ debe pasar por uno de los asientos donde los espectadores ~2, 4, 6, 8~ actualmente están sentados al salir del cine; por lo tanto, al menos uno de esos espectadores lo odiará.

Finalmente los espectadores restantes pueden salir del cine (en el orden ~4 , 8, 6, 2~) sin pasar por ningún asiento ocupado (en realidad, pueden salir del cine sin pasar por ningún asiento).

Ejemplo de entrada 2:

4
6 7 1 4 13 16 10 9 5 11 12 14 15 2 3 8

Ejemplo de salida 2:

3

Ejemplo de entrada 3:

6
11 21 35 22 7 36 27 34 8 20 15 13 16 1 24 3 2 17 26 9 18 32 31 23 19 14 4 25 10 29 28 33 12 6 5 30

Ejemplo de salida 3:

11