1912: 奶牛跑圈

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:12 通过:1

题目描述

农夫约翰让 N 头牛在长度为 C 的跑道上进行跑 L 圈的比赛。
有牛从同一起点,第 i 头牛的速度位 S_i 。 
当跑得最快的那一头牛跑完 L 圈时,所有牛才同时停下。 
超越事件:在比赛结束前某时刻,奶牛 x 已经超越了奶牛 y 整整一圈,则称做一次“超越事件”。 
注:至少一圈,超越了 1 / 2 圈,或者超越 1 / 4 圈等等都不算。
且对于同一对奶牛(x,y)不会重复计算次数。 
约翰想知道比赛过程中发生了多少次“超越事件”。

输入格式

第 1 行:N、L、C,1 <= n <= 100,000,1 <= l,c <= 25,000。
第 2 行 - 第 N + 1 行:第 i + 1 行包含速度 S_i,1 <= S_i <= 1,000,000。

输出格式

输出一个整数表示答案。

输入样例 复制

4 2 100
20
100
70
1

输出样例 复制

4

数据范围与提示

时间持续:2个单位(由第 2 头牛最先完成)。
在此期间发生4次超越事件:牛2超越了牛1和牛4,牛3超越了牛1和牛4。
来源:USACO 2012 OPEN