Atasco en las vías
Aunque el Ferrocarril de Stockton y Darlington inaugurado en 1825 ha pasado a la historia como el primero abierto al público en usar locomotoras de vapor, la realidad es que en sus orígenes nadie pensaba en otra cosa que en el uso de la fuerza motriz de los caballos. Cuando en 1821 el parlamento inglés aprobó la ley que autorizaba su construcción no se mencionaban las locomotoras de vapor por ningún sitio. Es más, el sello que diseñaron los promotores ese mismo año mostraba unos cuantos vagones tirados por un equino. La promoción del uso de caballos potenciaba una fuente lucrativa de ingresos que la propia ley permitía explícitamente: cualquier persona con vehículos apropiados podía montarlos en la vía y utilizarla tras el pago de un peaje.
El resultado, cuando los dueños decidieron que introducirían máquinas de vapor, fueron momentos de auténtico caos. Ha llegado a nuestros días que en 1830 la vía era utilizada por 50 caballos que compartían el tráfico con 19 locomotoras, cada una viajando a distinta velocidad. Una regulación del tráfico obligaba a los conductores de los trenes tirados por caballos a dejar pasar a trenes a vapor, más rápidos, pero muchos hacían caso omiso y no cogían las "vías auxiliares" construidas para ello. De hecho, se daban situaciones impensables hoy en día, como conductores que dejaban carruaje y caballo "aparcado" en la vía mientras se iban a tomar algo en algún local cercano o disputas de conductores que se resolvían a puñetazos a pie de vía mientras el caballo y los vagones bloqueaban el tráfico. Con este panorama no es de extrañar que fueran habituales los accidentes con trenes que atropellaban y mataban caballos.
Afortunadamente, los accidentes fueron minoritarios, pues no había muchos conductores irresponsables parándose donde les apetecía. Pero sí era habitual la existencia de jinetes poco respetuosos con la ley que no dejaban pasar a locomotoras más rápidas. El resultado era que se formaban grupos de trenes viajando todos a la velocidad del primer convoy del grupo, más lento.
Entrada
La entrada está formada por distintos casos de prueba, cada uno con dos líneas.
La primera línea de cada caso contiene el número N de trenes en la vía (hasta 500.000). La segunda línea tiene la velocidad a la que avanzaba cada convoy (hasta 109). Para nuestro análisis en el que nadie cede el paso para ser adelantado, no es relevante saber cuál era tirado por caballos y cual por locomotora de vapor.
Ten en cuenta que la vía está descrita desde el punto de salida, es decir el primer convoy que aparece es el último que salió de forma que, si su velocidad es mayor que el que lo precede en la vía (el segundo de la entrada), deberá reducirla.
Salida
Por cada caso de prueba se escribirá una línea con un único número que indica el número de grupos de trenes que se forman si nadie cede el paso a nadie y la vía es lo suficientemente larga como para que los más rápidos alcancen a los más lentos.
Entrada de ejemplo
3 3 2 1 3 2 1 3
Salida de ejemplo
1 2
Notas
En el primer caso del ejemplo tanto el tren con velocidad 3 como el de velocidad 2 se ven taponados por el de velocidad 1, formando un único grupo. En el segundo caso el tren con velocidad 1 tapona al de velocidad 2, formando un grupo mientras que el de velocidad 3 tiene vía libre y forma un grupo independiente.