Ranking modificado

Tras ayudar a corregir el sistema de emparejamiento, Karel descubre que Glitch también modificó la tabla de posiciones de NEXUS. Los jugadores deberían aparecer en el orden de su clasificación, pero la entidad intercambió sus lugares para hacer que el ranking pareciera imposible.

Los creadores de NEXUS te han pedido que les ayudes a calcular qué tan alterado está el ranking. Para medir su nivel de corrupción, deberás contar la cantidad de inversiones. Una inversión es una pareja de jugadores cuyo orden fue alterado. Supón que el jugador ~A~ debe aparecer antes que el jugador ~B~. Si en la lista modificada por Glitch el jugador ~B~ aparece antes que el jugador ~A~, esa pareja se considera invertida y aumenta en ~1~ el nivel de corrupción.

Karel debe calcular ese nivel para que NEXUS pueda seguir el rastro de Glitch hasta el núcleo del servidor.

Problema

En la primera fila del mundo hay montones de zumbadores con los números del ~1~ al ~N~ en algún orden. El montón en la columna ~i~ tiene ~A_i~ zumbadores.

Una pareja de columnas ~(i,j)~ se considera una inversión si se cumplen las dos condiciones siguientes:

• ~i<j~; es decir, la columna ~i~ está antes que la columna ~j~.
• ~A_i>A_j~; es decir, el valor en la columna ~i~ es mayor que el valor en la columna ~j~.

El nivel de corrupción es la cantidad total de inversiones de la permutación. Observa que cada pareja se cuenta sólo una vez.

Tu programa debe dejar un montón con exactamente el nivel de corrupción de la lista en columna ~1~ de la fila ~2~.

Entrada

En el ejemplo, los valores en la primera fila son: ~[4,1,6,2,5,3]~. La segunda fila comienza vacía.

Salida

Las parejas de columnas que están invertidas son:

• ~(1,2)~, ~(1,4)~ y ~(1,6)~;
• ~(3,4)~, ~(3,5)~ y ~(3,6)~;
• ~(5,6)~.

En total hay ~7~ inversiones. Por lo tanto, Karel deja un montón de ~7~ zumbadores en la posición ~(1,2)~.

Consideraciones

• Karel inicia en la posición (1,1) viendo hacia el Norte.
• Karel lleva INFINITOS zumbadores en la mochila.
• En la primera fila hay ~N~ montones sin espacios entre ellos.
• Los valores de los montones forman una permutación de los números del ~1~ al ~N~.
• El mundo es un cuadrado de ~100 \times 100~ sin paredes internas.
• Para este problema puedes utilizar un máximo de 12 variables por instrucción.
• Para obtener los puntos de este problema, únicamente importan los zumbadores en la posición ~(1, 2)~; la posición y orientación final de Karel no importan.

Subtareas

• ⭐ Subtarea 1 (25 puntos): La permutación está ordenada de menor a mayor o de mayor a menor.
• Subtarea 2 (25 puntos): Sin consideraciones adicionales.
• Subtarea 3 (25 puntos): Karel puede ejecutar la instrucción avanza/move() como máximo ~(N + 1)^2~ veces.
• Subtarea 4 (25 puntos): Karel puede ejecutar la instrucción avanza/move() como máximo ~22N + 1~ veces.