K. K-token Language Optimization
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sebastian is working on optimizing a system for Automatic Speech Recognition (ASR), and he's faced with a challenging task in improving the efficiency of speech data segmentation. Given a sequence of integer tokens representing features extracted from speech, his goal is to partition this sequence into the smallest number of contiguous subarrays such that each subarray contains at most $$$k$$$ unique elements.

In the context of ASR, each subarray represents a segment of speech, and the number of unique tokens in a segment must be limited to prevent overwhelming the system's memory and computational resources. Sebastian needs to minimize the number of such segments required while ensuring that each segment remains within the constraints for efficient processing.

Given an array $$$a$$$ of size $$$n$$$ (where $$$a_i$$$ is the token representing a feature in the ASR system) and an integer $$$k$$$ (the maximum number of unique tokens allowed in a segment), Sebastian must determine the minimum number of subarrays such that each subarray contains at most $$$k$$$ unique tokens.

Input
  • The first line contains two integers $$$n, k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq min(1000, n)$$$) — the size of the array and the maximum amount of unique tokens each subarray can contain.
  • The second line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \leq a_i \leq 1000$$$) representing the array of tokens.
Output

An integer representing the minimum number of contiguous subarrays that can be formed, each containing at most $$$k$$$ unique elements.

Examples
Input
3 1
1 2 3
Output
3
Input
3 2
1 2 3
Output
2
Input
3 1
1 1 1
Output
1