Para este problema se quiere conocer el costo asociado a diferentes implementaciones de una lista, usando la representación de arreglos y listas encadenadas simples. Para esto se realizarán operaciones de inserción, consulta, búsqueda y eliminación de valores en la lista. A continuación se muestra el costo de cada operación:

• Inserción: El costo de insertar un dato es la cantidad de pasos que se tenga que hacer en la lista, es decir, ya sea para buscar la posición donde se desea insertar o para mover valores que permitan insertar uno nuevo.
• Consultar: El costo de consultar una posición es la cantidad de pasos que se gasta para llegar hasta el índice de la posición consultada.
• Eliminar: El costo de eliminar una posición es la cantidad de pasos que se tenga que hacer en la lista, es decir, ya sea para llegar a la posición a eliminar o para mover valores y reorganizar la lista (en caso de ser necesario).
• Buscar: El costo de buscar un valor es la cantidad de pasos que se hacen para buscar la primera aparición del valor en la lista. En caso de no existir el valor buscado, el costo es la cantidad de pasos hechos para determinar que no existe el valor.

NOTA: Tenga en cuenta que dependiendo de la representación el costo cambia.

Para la entrada del problema usted debe implementar los siguientes comandos:

Comando 1:

• insertar x pos: indica que se va a agregar el valor x en la posición ‘pos’, si la posición en donde se quiere insertar no es válida, se debe imprimir ‘insertar: posicion invalida’, en otro caso imprimir ‘insertar: posicion valida’. La primera posición de la lista es la posición 0.

Comando 2:

• consultar pos: Consiste en revisar qué valor se encuentra en la posición ‘pos’ de la lista e imprimirlo según el formato de salida (ver ejemplo). En caso de no existir la posición se debe imprimir “consulta: no encontrado”

Comando 3:

• eliminar pos: indica que se va a eliminar el valor en la posición ‘pos’, si la posición en donde se quiere eliminar no es válida, se debe imprimir ‘eliminar: posicion invalida’. Si se puede eliminar correctamente se debe imprimir ‘eliminar: posicion valida’.

Comando 4:

• buscar x: indica que se va a buscar la primera aparición del valor ‘x’ en la lista. Si se encuentra al menos una ocurrencia del valor ‘x’ se debe imprimir la posición en el formato de salida (“buscar: X” - ver ejemplo), en caso contrario se debe imprimir “no existe numero”. Nótese que las palabras “posicion” y “numero” no deben tener tilde en el mensaje de salida.

Comando 5:

• costo: Este comando debe imprimir la palabra ‘costo’ seguida de ‘:’ seguida de 2 valores separados por un espacio. El primero es el costo acumulado hasta el momento utilizando arreglos y el segundo es el costo acumulado hasta el momento utilizando listas encadenadas simples.

Entrada

La primera línea es un número T que representa la cantidad de casos de prueba. Cada caso de prueba inicia con una línea con un entero N que representa la cantidad de comandos que siguen. Luego siguen N líneas cada una con un comando como los descritos anteriormente.

Restricciones/Consideraciones

0 < T < 1000
1≤ N ≤10000

Salida

Se debe imprimir según la descripción de cada comando. Cada caso de prueba debe comenzar con una línea “Caso #” seguido del número del caso y “:”.