Problem 32: Subarray Distinct Values

Problem Statement: Given an array of n integers and a window size k, for each contiguous subarray of size k, determine the number of distinct integers in that subarray.

Input

The first line contains two integers n and k. The second line contains n space-separated integers.

Output

Print n-k+1 integers, where the i-th integer is the number of distinct elements in the i-th subarray of size k.

Examples


Input:
7 4
1 2 1 3 4 2 3

Output:
3 4 4 3

Solution in C++


#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k; cin >> n >> k;
    vector<int> a(n);
    for (int i=0; i<n; i++) cin >> a[i];
    unordered_map<int,int> freq;
    int distinct = 0;
    for(int i = 0; i < k; i++){
        if(freq[a[i]] == 0) distinct++;
        freq[a[i]]++;
    }
    cout << distinct;
    for(int i = k; i < n; i++){
        freq[a[i-k]]--;
        if(freq[a[i-k]] == 0) distinct--;
        if(freq[a[i]] == 0) distinct++;
        freq[a[i]]++;
        cout << " " << distinct;
    }
    cout << "\n";
    return 0;
}