Chán đua ngựa, Farmer John quyết định nghiên cứu tính khả thi của môn đua bò. Ông cho \(N\) con bò (\(1 \le N \le 100\,000\)) chạy một cuộc đua gồm \(L\) vòng quanh đường đua hình tròn có độ dài \(C\). Tất cả bò xuất phát tại cùng một điểm trên đường đua và chạy với các vận tốc khác nhau; cuộc đua kết thúc khi con bò nhanh nhất đã chạy đủ tổng quãng đường \(LC\).

FJ nhận thấy nhiều lần một con bò vượt qua một con khác và tự hỏi loại "sự kiện vượt nhau" này xảy ra bao nhiêu lần trong toàn bộ cuộc đua. Cụ thể hơn, một sự kiện vượt nhau được xác định bởi một cặp bò \((x,y)\) và một thời điểm \(t\) (nhỏ hơn hoặc bằng thời điểm kết thúc cuộc đua), tại đó bò \(x\) vượt lên trước bò \(y\). Hãy giúp FJ đếm tổng số sự kiện vượt nhau trong toàn bộ cuộc đua.

Dữ liệu vào

• Dòng 1 chứa ba số nguyên \(N\), \(L\) và \(C\), cách nhau bởi dấu cách (\(1 \le L,C \le 25\,000\)).
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa vận tốc của con bò \(i\), là một số nguyên trong khoảng từ 1 đến \(1\,000\,000\).

Dữ liệu ra

• Dòng 1 chứa tổng số sự kiện vượt nhau trong toàn bộ cuộc đua.

Ví dụ

4 2 100
20
100
70
1

4

Nguồn

USACO 2012 US Open, Silver Division — Running Laps

Tác giả: Brian Dean, 2012.