After setting all his ideas for bugaboos, Max has decided to blindly steal from others he saw online.
Recently, he read an interesting bugaboo on a new online judge called JOMD:
Given an array of length
,
, find the number of subarrays
![]()
such that
.
Note: denotes the maximum value in the range
in
; likewise,
denotes the minimum value in the range
in
.
This bugaboo stumped Max, so he asked you for help.
Can you help him?
Constraints
Subtask 1 [20%]
Subtask 2 [80%]
Note: Fast I/O might be required to fully solve this problem (e.g., BufferedReader for Java).
Input Specification
The first line will contain ,
, and
, the number of elements in the array and the minimum and maximum difference between the maximum and minimum in the subarrays.
The next line will contain space-separated integers, the elements of the array.
Output Specification
Output the number of distinct subarrays that have a difference between the maximum and minimum in .
Sample Input
8 3 3
1 4 5 2 2 -3 -5 -6
Sample Output
6
Explanation for Sample Output
There are distinct subarrays that have a difference of exactly
:
.
Comments