Meter variety windows: hints, no solution

A district has many meters, each with a numeric id. Every time a meter reports, its id is appended to a log, so the log lists ids in the order the reports arrived and the same meter can appear many times.

A window is k consecutive entries of the log. Given the log, k and a number m, count the windows that contain at least m distinct meter ids. Windows are counted by their position, so two windows with the same content at different places count twice. If the log is shorter than k, the answer is 0.

Examples

Input

meters = [1, 2, 1, 3, 3, 2], k = 3, m = 2

Output

4

Note

Windows [1,2,1], [2,1,3], [1,3,3] and [3,3,2] each have at least two distinct ids.

Input

meters = [1, 2, 1, 3, 3, 2], k = 3, m = 3

Output

1

Note

Only the window [2,1,3] holds three distinct ids.

Input

meters = [4, 5, 6], k = 2, m = 3

Output

0

Note

A window of 2 entries cannot hold three distinct ids.

Constraints

• 0 <= meters.length <= 50000
• 1 <= meters[i] <= 100000
• 1 <= k <= 50000, 1 <= m <= 50000

Hint 1: a nudge

What do you have to know about a window to say how many distinct ids it holds, and how does that change when the window moves by one entry?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing