Ordenamiento de la comida


Submit solution


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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Los N\,(1 \leq N \leq 10\,000) tipos de comida de Ponyo están alineados para el banquete de la tarde. Cada comida tiene un nivel único de “mal sabor” en el rango 1...100,000. Debido a que las comidas con mal sabor son más propensas a dañar la digestión, Ponyo quisiera reordenar las comidas en la línea de tal manera que estén alineadas en orden ascendente de mal sabor. Durante este proceso, los lugares de dos comidas cualesquiera (no necesariamente adyacentes) pueden ser intercambiados. El intercambio de lugar de dos comidas es algo complicado, ya que Ponyo debe emplear X+Y unidades de tiempo intercambiar dos comidas cuyos niveles de mal sabor sean X y Y.

Ayude a Ponyo a calcular el tiempo mínimo requerido para reordenar a las comidas.

Entrada

  • Línea 1: Un solo entero: N.
  • Líneas 2..N+1: Cada línea contiene un solo entero: la línea i+1 describe el mal sabor de la comida i.

Salida

Una sola línea con el tiempo mínimo requerido para reordenar las comidas en orden creciente de mal sabor.

Ejemplo de entrada

3
2
3
1

Ejemplo de salida

7

Explicación

Entrada

Tres comidas están en la línea con niveles de mal sabor respectivamente 2, 3, y 1.

Salida

2 3 1 : Orden inicial.

2 1 3 : Después de intercambiar las comidas con mal sabor 3 y 1 (tiempo=1+3=4).

1 2 3 : Después de intercambiar las comidas con mal sabor 1 y 2 (tiempo=2+1=3).


Comments

There are no comments at the moment.