Joker


Submit solution


Points: 100 (partial)
Time limit: 4.0s
Java 8 6.0s
Python 12.0s
Memory limit: 1G

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Prolog, Python, Swift, VB

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

Comments

There are no comments at the moment.