{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eEn una antigua estación de tren, es posible que todavía se encuentre con uno de los últimos \"intercambiadores de trenes\" que quedan. Un intercambiador de trenes es un empleado del ferrocarril, cuyo único trabajo es reorganizar los vagones de los trenes.\u003c/p\u003e\n\n\u003cp\u003eUna vez que los vagones están dispuestos en el orden óptimo, todo lo que tiene que hacer el conductor del tren es dejar los vagones, uno por uno, en las estaciones para las que está destinada la carga.\u003c/p\u003e\n\n\u003cp\u003eEl título \"intercambiador de trenes\" proviene de la primera persona que realizó esta tarea, en una estación cercana a un puente ferroviario. En lugar de abrirse verticalmente, el puente giraba alrededor de un pilar en el centro del río. Después de girar el puente $90$ grados, los barcos podrían pasar a la izquierda o a la derecha.\u003c/p\u003e\n\n\u003cp\u003eEl primer intercambiador de trenes había descubierto que el puente podía funcionar con dos vagones como máximo. Al girar el puente 180 grados, los vagones cambiaron de lugar, lo que le permitió reacomodar los vagones (como efecto secundario, los vagones miraron en la dirección opuesta, pero los vagones de tren pueden moverse en ambos sentidos, así que a quién le importa).\u003c/p\u003e\n\n\u003cp\u003eAhora que casi todos los intercambiadores de trenes han desaparecido, a la compañía ferroviaria le gustaría automatizar su operación. Parte del programa a desarrollar, es una rutina que decide para un tren dado el menor número de permutas de dos vagones adyacentes necesarios para ordenar el tren. Tu tarea es crear esa rutina.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"La entrada contiene en la primera línea el número de casos de prueba ($N$). Cada caso de prueba consta de dos líneas de entrada. La primera línea de un caso de prueba contiene un entero $L$, que determina la longitud del tren ($0\\leq L\\leq 50$). La segunda línea de un caso de prueba contiene una permutación de los números del $1$ al $L$, lo que indica el orden actual de los carros. Los carros deben pedirse de manera que el carro $1$ venga primero, luego el $2$, etc. y el carro $L$ llegue al final."}},{"title":"Output","value":{"format":"HTML","content":"Para cada caso de prueba, muestre por pantalla la sentencia: ``Optimal train swapping takes S swaps\u0027\u0027 donde $S$ es un entero."}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3\n1 3 2\n4\n4 3 2 1\n2\n2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\nOptimal train swapping takes 1 swaps.\nOptimal train swapping takes 6 swaps.\nOptimal train swapping takes 1 swaps.\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}