题目描述

学校的校道上种了 $n$ 棵树，编号为 $1 \sim n$，每棵树都有自己的品种，假设第 $i$ 棵树的品种是 $a_i$。小晓想在其中选择连续 $k$ 棵树进行装饰，以便营造书香氛围。不过因为小晓喜欢偶数且不希望树的种类过少而显得单调，所以她希望这连续 $k$ 棵树里至少有 $x$ 个不同品种的树的数量是偶数，请问她有多少种选取方案？

输入格式

共两行，第一行三个正整数 $n$，$k$，$x$

第二行 $n$ 个正整数，为数的品种 $a_i$

数据范围

50% 数据 $1 \le x \lt k \le n \le 1000$

100% 数据 $1 \le x \lt k \le n \le 1000000$，$1 \le a_i \le 10000$

输出格式

一个正整数，为可选取的方案数。

样例

10 6 2
1 2 2 1 3 4 3 5 5 8

4

样例解释

4 种可选取的方案分别为：(1 2 2 1 3 4) 、(2 2 1 3 4 3)、(1 3 4 3 5 5)、(3 4 3 5 5 8)