User's AC Ratio

90.9% (10/11)

Submission's AC Ratio

54.3% (19/35)

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

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