El mozo de estación

Cuando, ahora que está apunto de completar su título universitario, ha visto que en las ofertas de empleo que llegan a su facultad hay una de mozo de estación, se le ha caído el alma a los pies. Después de tanto esfuerzo y sufrimiento estudiando asignaturas con el objetivo de abaratar los costes de producción de empresas industriales, no esperaba que le llegaran ofertas de ese tipo.

Sin embargo, cuando después ha visto en qué consiste exactamente el empleo, ha entendido que el trabajo en cuestión requiere educación superior. Si se hace bien, se consigue un ahorro brutal en consumo de energía y se reduce la contaminación de la zona.

El trabajo consiste en enfrentarse, diariamente, a una casi-infinita fila de coches esperando ansiosos a ser subidos a un tren que les llevará al otro lado del país. El tren permite que los coches suban o bien por la parte delantera o por la parte trasera, por lo que se debe, en pocos segundos, decidir por orden de llegada, si le pide al siguiente coche en la fila que suba por uno u otro lado del tren.

Contado así no parece difícil. Podría basar su decisión en el lanzamiento de una moneda, la paridad de la matrícula o cualquier otro criterio. El problema es que hay otra restricción. Para garantizar la seguridad del tren, los coches deben ir por orden decreciente de peso: el más pesado irá al lado de la locomotora (entrará el último por el lado de la cabeza) y el más ligero irá al final del todo (entrará el último por el lado trasero).

Teniendo en cuenta esa restricción y que los coches de la fila no pueden reordenarse, nuestro mozo de estación tiene que decidir si el coche va para un lado u otro del tren o si, para que los coches queden ordenados por peso, se tendrá que "quedar en tierra" a esperar al próximo tren. Que le cojan o no en el trabajo depende de si es capaz de cargar el tren con el mayor número de coches posible.

Entrada

Salida

Entrada de ejemplo

4
1 2 3 4
5
2 3 1 4 5
6
2 3 6 1 4 5
0

Salida de ejemplo

4
5
5