250,000 rockets racing in parallel tracks across space. Each rocket i has a starting position x_i and a constant velocity v_i (bounded by 100) with which it will move. Assume that the rockets are enumerated in order of their starting position.

Thus, initially the rockets are lined up as:

-----x---------------------------------------------------------> (x1,v1) ---------x-----------------------------------------------------> (x2,v2) ----------------x----------------------------------------------> (x3,v3) .... ---------------------------x------------------------------------> (x250000,v250000)

**Constraints**

- At any given time, no more two rockets are at the same position. This implies that all overtakings take place at distinct times.
- The race goes on forever. Eventually, faster rockets overtake slower rockets and beyond a point the rockets will become ordered in the order of their velocities.

**Problems**

- Compute the number of overtakings (modulo 1000000, say) in the eventual race.
- Print out the first 10,000 overtakings (in order).

©IARCS 2012–2016

PÄ›stujeme web | visit: Skluzavky