Joker
Esta noche, en tu cine favorito están dando la película Joker y todos los asientos están ocupados. En el cine hay filas con asientos cada una, formando un cuadrado \(N × N\). Denotamos con los espectadores en la primera fila (de izquierda a derecha); con los espectadores en la segunda fila (de izquierda a derecha); y así sucesivamente hasta la última fila, cuyos espectadores se indican con .
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 . El espectador espera hasta que el espectador 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 pase por un asiento actualmente ocupado por el espectador ; en ese caso, el espectador odiará al espectador 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 tal que odiará para siempre.
Restricciones
La secuencia es una permutación de .
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 .
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 pueden salir del cine sin pasar por ningún asiento, para que nadie los odie.
Entonces, espectador debe pasar por uno de los asientos donde los espectadores 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 ) 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