TopCoder

User's AC Ratio

87.5% (14/16)

Submission's AC Ratio

33.8% (25/74)

Description

普遜是一隻喜歡吃飯和睡覺的貓貓,不過牠有時會用剩餘的時間開著直升機到處逛逛。

有天,普遜注意到了蓬萊東路上有不少高樓大廈,這些高樓大廈排成一直線,相鄰的兩棟大樓的距離皆為一公尺。為了消磨時間,普遜決定去那兒開直升機。因為起飛跟降落是非常高難度的動作,因此普遜只打算從其中一棟高樓的頂樓出發,以直線飛行到另一棟樓的屋頂,並停在該棟高樓的頂樓,並且把直升機留在那裡,自己搭電梯下樓後回家睡覺。

然而,由於普遜的飛行技術不是很好,因此牠必須慎選飛行的路線。普遜思考了自己的飛行技術之後決定,自己只能接受飛行過程中,斜率的絕對值不到 $U$ 的路線,但是如果飛行過程中太平坦好像也太沒有挑戰性了,因此牠希望飛行路線的斜率的絕對值至少要有$L$ 。換句話說,如果兩棟大樓底部的距離是 $x$,兩棟大樓的高度差是 $y$,那麼普遜只能接受 $L\leq \lvert y/x \rvert < U$的路線。符合普遜要求的路線顯然有非常多種,因此普遜開始好奇:在蓬萊東路上,究竟有多少條這樣的路線呢?附註:在普遜的心目中,僅僅是把起點與終點互換不算是兩條不一樣的路線。

Input Format

測試資料共包含兩行。
第一行有三個整數$N,L,U$,分別表示蓬萊東路的高樓數以及普遜能夠接受的斜率。第二行有$N$個整數,第$i$個數字$y_i$表示距離蓬萊東路路口$i$公尺處有一棟高度為$y_i$公尺的大樓。

  • $2\leq N \leq 10^ 5$
  • $0\leq y_i \leq 10^ 9$
  • $0\leq L < U \leq 10^ 9$

Output Format

請輸出一行包含一個整數,表示普遜可以接受的飛行路線的數量。

Sample Input

6 1 3
8 7 1 2 2 8

Sample Output

7

Hints

Problem Source

2016 NPSC高中組決賽

Subtasks

No. Testdata Range Score
1 0~36 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1000 262144 262144 1
6 1000 262144 262144 1
7 1000 262144 262144 1
8 1000 262144 262144 1
9 1000 262144 262144 1
10 1000 262144 262144 1
11 1000 262144 262144 1
12 1000 262144 262144 1
13 1000 262144 262144 1
14 1000 262144 262144 1
15 1000 262144 262144 1
16 1000 262144 262144 1
17 1000 262144 262144 1
18 1000 262144 262144 1
19 1000 262144 262144 1
20 1000 262144 262144 1
21 1000 262144 262144 1
22 1000 262144 262144 1
23 1000 262144 262144 1
24 1000 262144 262144 1
25 1000 262144 262144 1
26 1000 262144 262144 1
27 1000 262144 262144 1
28 1000 262144 262144 1
29 1000 262144 262144 1
30 1000 262144 262144 1
31 1000 262144 262144 1
32 1000 262144 262144 1
33 1000 262144 262144 1
34 1000 262144 262144 1
35 1000 262144 262144 1
36 1000 262144 262144 1