Running Laps

Farmer John decides to investigate whether cow racing could work as a sport. He lines up his $N$ cows ($1 \le N \le 100{,}000$) to run a race of $L$ laps around a circular track of length $C$. All cows start at the same point and each runs at its own constant speed. The race ends the moment the fastest cow has covered the full distance $L \cdot C$.

During the race one cow may pass another. A crossing event is defined by an ordered pair of cows $(x, y)$ and a time $t$ (no later than the moment the race ends) at which cow $x$ moves ahead of cow $y$. Count the total number of crossing events that occur during the entire race.

• Line 1: three space-separated integers $N$, $L$, and $C$ ($1 \le L, C \le 25{,}000$).
• Lines 2 to $N+1$: line $i+1$ contains the speed of cow $i$, an integer between $1$ and $1{,}000{,}000$.

• A single line with the total number of crossing events during the entire race.

Consider 4 cows running 2 laps on a track of length 100 with speeds 20, 100, 70, and 1. The race lasts until the fastest cow (speed 100) finishes its 2 laps. During that time there are 4 crossing events: the speed-100 cow passes the speed-20 and speed-1 cows, and the speed-70 cow also passes the speed-20 and speed-1 cows.