Least Toffee Variety

Problem Statement

Least Toffee Variety Problem Description Lena loves toffees, and every day, her mother gives her one. She's collected M toffees in a row, each from one of M different types. Now, Lena will eat at least K consecutive toffees to enjoy. The fewer her toffees in that group, the happier she'll be. Can you help Lena find the group of toffees with the least variety so she can be as happy as possible? Input Format The first line contains an integer N, M, and K, respectively, where N is the number of toffees, M is the number of different types of toffees, and K is the least number of consecutive toffees Lena wants to enjoy. The second line contains N integers, t[1] (1 ≤ t[i] ≤ M), where t[i] represents the type of the i-th toffee. Output Format Print a single integer, which is the minimum number of different types of toffees Lena gets to eat. Constraints 1 ≤ N ≤ 10^5 1 ≤ M ≤ 10^6 1 ≤ K ≤ N 1 ≤ t[i] ≤ M Examples Example 1: Input: 3 4 2 4 1 1 Output: 2 Explanation: I