Vigilando el Museo


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

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

Para proteger las obras de arte del Museo de IslaGrande, se han instalado N (1 \le N \le 10^5) cámaras de vigilancia de un nuevo tipo. El museo puede representarse como una matriz cuadrada de tamaño N \times N y cada cámara, siendo de un tipo especial, puede vigilar todas las celdas que están encima o a la izquierda de esta. Una obra está bien protegida si es vigilada por exactamente dos cámaras. Dos cámaras no ocupan la misma fila o la misma columna.

Se quiere contar la cantidad de posiciones en que se puede colocar una obra para que este bien protegida.

Entrada

La primera línea de la entrada contine un entero N.

La segunda línea contiene N números diferentes en el rango 1..N. El i-ésimo entero representa la columna en la que se ha instalado la cámara de la fila i-ésima.

Salida

Un solo entero: la cantidad de posiciones en que se puede colocar una obra para que este bien protegida.

Ejemplo de Entrada

9
5 9 1 8 2 6 4 7 3

Ejemplo de Salida

20

Explicación del Ejemplo

El diagrama representa el museo. Las posiciones con una 'x' son posiciones bien vigiladas. Las posiciones con '*' son las celdas que contienen cámaras.

x x x x * _ _ _ _
x x x x _ x x x *
* _ _ _ _ _ _ _ _
_ x x x _ x x * _
_ * _ _ _ _ _ _ _
_ _ x x _ * _ _ _ 
_ _ x * _ _ _ _ _ 
_ _ x _ _ _ * _ _ 
_ _ * _ _ _ _ _ _

Comments

There are no comments at the moment.