Cerință

Un șir $s_1, s_2, \ldots, s_k$ de numere naturale se numește $xy$-dominant pentru niște valori $x$ și $y$ date dacă:

1. Există cel puțin $x$ numere distincte în șirul $s$.
2. Se pot alege $x$ numere distincte din șir astfel încât suma frecvențelor numerelor alese să fie mai mare sau egală cu $y$.

De exemplu, pentru $x=2$ și $y=4$:

• șirul $[1,2,1,2,3]$ este $xy$-dominant (putem alege numerele $1$ și $2$, care apar în șir în total de $2+2=4$ ori).
• șirul $[1,1,1,1]$ nu este $xy$-dominant (nu există două valori distincte în șir).
• șirul $[1,2,1,3]$ nu este $xy$-dominant (nu există două valori distincte în șir care să apară în total de cel puțin $4$ ori).

Se dau $n, x, y$ și un șir de numere naturale $a_1, a_2, \ldots, a_n$.

Aflați numărul de subsecvențe $xy$-dominante ale șirului $a$.

Date de intrare

Pe prima linie a fișierului dominant.in se află numerele $n$, $x$ și $y$.

Pe a doua linie se află șirul $a_1, a_2, \ldots, a_n$.

Date de ieșire

Pe prima linie a fișierului dominant.out se va afișa numărul de subsecvențe $xy$-dominante ale șirului $a$.

Restricții și precizări

• $1 \leq n \leq 3 \cdot 10^5$
• $1 \leq x \leq$ numărul de valori distincte din șirul $a$
• $1 \leq y, a_i \leq n$
• Pentru a obține punctele pentru un anumit subtask, cel puțin o sursă trimisă va trebui să treacă toate testele din acel subtask.

  #	Punctaj	Restricții
  0	0	Exemple
  1	25	$1 \leq n \leq 300$
  2	22	$1 \leq n \leq 3 \ 000$
  3	16	$y = 1$
  4	19	$x = 1$
  5	18	Fără alte restricții

Exemplul 1

dominant.in

4 3 1
1 2 3 4

dominant.out

3

Explicație

Subsecvențele $xy$-dominante sunt $[1,2,3]$, $[2,3,4]$ și $[1,2,3,4]$.

Exemplul 2

dominant.in

10 2 4
1 1 1 2 1 2 2 2 1 2

dominant.out

28

Explicație

În total sunt $28$ de subsecvențe $xy$-dominante, printre care se numeră $[1,1,1,2]$, $[2,1,2,2]$ și $[1,1,1,2,1,2,2,2,1,2]$.

Exemplul 3

dominant.in

14 3 8
5 3 5 1 4 5 1 4 2 2 4 5 4 4

dominant.out

15

Explicație

În total sunt $15$ subsecvențe $xy$-dominante, cum ar fi $[5,3,5,1,4,5,1,4,2,2,4]$.