Problem 3918: SecvMEX

După o vacanță de vară plină de distracție și relaxare, Zăhărel a revenit la școală, hotărât să se pregătească pentru Olimpiada Națională de Informatică. In prima sa lecție, profesoara a explicat ce este MEX-ul unei secvențe: "MEX-ul unei secvențe este cel mai mic numar pozitiv care nu se regăsește în secvență. Spre exemplu, MEX-ul subsecvenței 0 2 5 7 1 2 3 este 4, întrucât 0, 1, 2 și 3 apar în subsecvență."
Așadar, ca și temă, Zăhărel a primit următoarea problema:

Cerință

Se citesc de la tastatură $n$ , $k$ și $w$ numere naturale, urmate de șirul $v$ format din $n$ numere naturale. Calculați numarul de subsecvențe nevide care au MEX-ul mai mare sau egal decât $k$ și mai mic sau egal decât $w$ . O subsecvență se obține prin eliminarea unui prefix și/sau a unui sufix al șirului inițial.

Date de intrare

Pe prima linie se găsesc trei numere naturale, $n$ , $k$ și $w$ .
A doua linie conține șirul $v$ format din cele $n$ numere naturale.

Date de ieșire

Pe prima linie se va găsi un singur număr natural, numărul de secvențe cu MEX-ul între $k$ și $w$ .

Restricții și precizări

$1 \leq n \leq 1 \ 000 \ 000$ ;
Numerele din șirul v vor fi $\leq 2 \ 000 \ 000 \ 000$
Pentru teste în valoare de $10$ de puncte, $n \leq 1 \ 000 \ și \ v[i] \leq 1, \ 1 \leq i \leq n$
Pentru teste în valoare de $10$ de puncte, $n \leq 1 \ 000 \ 000 \ și \ v[i] \leq 1, \ 1 \leq i \leq n$
Pentru teste în valoare de $20$ de puncte, $n \leq 200$
Pentru teste în valoare de $20$ de puncte, $n \leq 1 \ 000$
Pentru teste în valoare de $10$ de puncte, $n \leq 1 \ 000 \ 000 \ , \ k = w = 0$
Pentru teste în valoare de $30$ de puncte nu există alte restricții

Exemplul 1

stdin

5 1 2
1 0 0 2 1

stdout

Explicație

Sunt $7$ subsecvențe cu MEX-ul între $1$ și $2$ : [1,0], [1,0,0], [0], [0,0], [0,0,2], [0], [0,2].

Exemplul 2