랩 경주

농부 John은 소 경주를 새로운 스포츠로 삼을 수 있을지 알아보려고 한다. 그는 $N$마리의 소($1 \le N \le 100{,}000$)를 둘레가 $C$인 원형 트랙에서 $L$바퀴 도는 경주에 출전시킨다. 모든 소는 같은 지점에서 동시에 출발하며, 각자 일정한 속도로 달린다. 가장 빠른 소가 총 거리 $L \cdot C$를 모두 달린 순간 경주가 끝난다.

경주 도중 한 소가 다른 소를 앞지르는 일이 생긴다. 추월 사건은 순서쌍 $(x, y)$와 시각 $t$(경주가 끝나는 시각 이하)로 정의되며, 시각 $t$에 소 $x$가 소 $y$를 앞질러 앞서 나가는 것을 뜻한다. 경주 전체 동안 일어나는 추월 사건의 총 횟수를 구하여라.

• 첫째 줄: 공백으로 구분된 세 정수 $N$, $L$, $C$ ($1 \le L, C \le 25{,}000$).
• 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄에는 소 $i$의 속도가 주어지며, $1$ 이상 $1{,}000{,}000$ 이하의 정수이다.

• 경주 전체 동안 발생한 추월 사건의 총 횟수를 한 줄에 출력한다.

소 4마리가 둘레 100인 트랙을 2바퀴 돌고, 속도가 각각 20, 100, 70, 1인 경우를 생각해 보자. 경주는 가장 빠른 소(속도 100)가 2바퀴를 마칠 때까지 이어진다. 그 동안 추월 사건은 모두 4번 일어난다. 속도 100인 소가 속도 20인 소와 속도 1인 소를 앞지르고, 속도 70인 소도 속도 20인 소와 속도 1인 소를 앞지른다.