URI Online Judge | 2095

Guerra

Por Joaquin Rodrigues, Universidad Nacional de La Plata AR Argentina

Timelimit: 1

La guerra, evento solamente digno de aparecer en la literatura, películas o quizás problemas de competencias de programación, llegó al imperio de Nlogonia, que se enfrenta al vecino imperio de Quadradonia. Los protocolos de guerra pautados por ambos imperios indican que la guerra será desarrollada en sucesivas batallas, y que en cada una de estas batallas se enfrentará un soldado distinto de cada imperio, de modo que cada soldado participará en exactamente una batalla. El imperio que gane la mayor cantidad de batallas ganará la guerra. Cada imperio posee un ejército conformado por S soldados, y cada soldado posee cierta habilidad para el combate. En cada batalla entre dos soldados, aquel con mayor habilidad para el combate gana la batalla. Si ambos soldados poseen la misma habilidad, la batalla resulta un empate y técnicamente ningún bando se adjudica la victoria. Los espías de Nlogonia interceptaron información secreta sobre la habilidad de cada soldado de Quadradonia, y la reina de Nlogonia requiere la ayuda de ustedes para saber la cantidad máxima de batallas que puede ganar en la guerra si envía a sus soldados en el orden adecuado.

Entrada

La primera línea contiene un entero S que indica la cantidad de soldados de cada imperio (1 ≤ S ≤ 105 ). La segunda línea contiene S enteros Qi que representan las habilidades de los distintos soldados de Quadradonia, en el orden en que se sucederán las batallas (1 ≤ Qi ≤ 109 para i = 1, 2, . . . , S). La tercera línea contiene S enteros Ni que representan las habilidades de los distintos soldados de Nlogonia, en un orden cualquiera (1 ≤ Ni ≤ 109 para i = 1, 2, . . . , S).

Salida

Imprimir en la salida una línea conteniendo un entero que representa la cantidad máxima de batallas que puede ganar Nlogonia en la guerra.

Ejemplos de Entrada Ejemplos de Salida

3

2 1 1000000000

1 1 2

1

4

6 3 1 4

2 7 4 3

3