Arithmetic Sequence

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

A sequence $b_1,b_2,\cdots,b_n$ are called $(d_1,d_2)$-arithmetic sequence if and only if there exist $i(1\leq i\leq n)$ such that for every $j(1\leq j<i),b_{j+1}=b_j+d_1$ and for every $j(i\leq j<n),b_{j+1}=b_j+d_2$.

Teacher Mai has a sequence $a_1,a_2,\cdots,a_n$. He wants to know how many intervals $[l,r](1\leq l\leq r\leq n)$ there are that $a_l,a_{l+1},\cdots,a_r$ are $(d_1,d_2)$-arithmetic sequence.

Input

There are multiple test cases.

For each test case, the first line contains three numbers $n,d_1,d_2(1\leq n\leq 10^5,|d_1|,|d_2|\leq 1000)$, the next line contains $n$ integers $a_1,a_2,\cdots,a_n(|a_i|\leq 10^9)$.

Output

For each test case, print the answer.

Sample Input

5 2 -2 0 2 0 -2 0 5 2 3 2 3 3 3 3

Sample Output

12 5

Hint

wange2014

Source

2015 Multi-University Training Contest 9

提交代码