Tổng Đoạn

Cho dãy số $S$ gồm $n$ số nguyên $S_1, S_2, ..., S_n$ và hai số nguyên $L, R$.

Hãy đếm số lượng cặp chỉ số $(i, j)$ thỏa mãn $1 ≤ i ≤ j ≤ n$ sao cho tổng các phần tử từ vị trí $i$ đến vị trí $j$ nằm trong đoạn $[L, R]$, nghĩa là:

$L ≤ \sum_{k=i}^{j} S_k ≤ R$

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $n$ ($1 ≤ n ≤ 10^5$), $L$ và $R$ ($-10^9 ≤ L ≤ R ≤ 10^9$).

Dòng thứ hai chứa $n$ số nguyên $S_1, S_2, ..., S_n$ ($-10^9 ≤ S_i ≤ 10^9$ với mọi $1 ≤ i ≤ n$).

Kết quả

In ra một số nguyên duy nhất là số lượng cặp chỉ số thỏa mãn điều kiện.

Chấm điểm

Subtask 1 (30 points). $n ≤ 2000$

Subtask 2 (30 points). $S_i ≥ 0$ với mọi $1 ≤ i ≤ n$

Subtask 3 (40 points). $1 ≤ n ≤ 10^5$

Ví dụ

Input

5 -1 3
2 -2 3 1 -1

Output

12

Ghi chú

Trong ví dụ mẫu, các cặp chỉ số $(i, j)$ thỏa mãn gồm có 12 cặp:

• $i = 1$: các cặp $(1, 1)$, $(1, 2)$, $(1, 3)$, $(1, 5)$.
• $i = 2$: các cặp $(2, 3)$, $(2, 4)$, $(2, 5)$.
• $i = 3$: các cặp $(3, 3)$, $(3, 5)$.
• $i = 4$: các cặp $(4, 4)$, $(4, 5)$.
• $i = 5$: cặp $(5, 5)$.