Untitled

import java.util.*;

public class MaxBeautyWithRepaints {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // Input number of blocks, number of queries, and maximum repaints
        int n = sc.nextInt();
        int q = sc.nextInt();
        int m = sc.nextInt();

        // Input the block colors
        int[] blockColors = new int[n];
        for (int i = 0; i < n; i++) {
            blockColors[i] = sc.nextInt();
        }

        // Input the favorite colors for the queries
        int[] favoriteColors = new int[q];
        for (int i = 0; i < q; i++) {
            favoriteColors[i] = sc.nextInt();
        }

        // Preprocess beauty values for each unique color
        Map<Integer, Integer[]> precomputedResults = preprocessBeautyValues(blockColors, n, m);

        // Answer each query using the precomputed results
        StringBuilder result = new StringBuilder();
        for (int favoriteColor : favoriteColors) {
            Integer[] beautyValues = precomputedResults.getOrDefault(favoriteColor, new Integer[m + 1]);
            result.append(beautyValues[m]).append("\n");
        }

        // Output the results
        System.out.println(result.toString());
        sc.close();
    }

    private static Map<Integer, Integer[]> preprocessBeautyValues(int[] blockColors, int n, int m) {
        Map<Integer, Integer[]> precomputedResults = new HashMap<>();

        // Get all unique colors in the blockColors array
        Set<Integer> uniqueColors = new HashSet<>();
        for (int color : blockColors) {
            uniqueColors.add(color);
        }

        // Precompute beauty values for each color
        for (int color : uniqueColors) {
            Integer[] beautyValues = new Integer[m + 1]; // For repaint counts 0 to m
            Arrays.fill(beautyValues, 0);

            // Sliding window to calculate maximum beauty for each repaint count
            int left = 0, repaintCount = 0, maxBeauty = 0;
            for (int right = 0; right < n; right++) {
                if (blockColors[right] != color) {
                    repaintCount++;
                }

                while (repaintCount > m) {
                    if (blockColors[left] != color) {
                        repaintCount--;
                    }
                    left++;
                }

                // Update maximum beauty for the current repaint count
                maxBeauty = Math.max(maxBeauty, right - left + 1);
                beautyValues[repaintCount] = maxBeauty;
            }

            // Fill the results for higher repaint counts
            for (int i = 1; i <= m; i++) {
                beautyValues[i] = Math.max(beautyValues[i], beautyValues[i - 1]);
            }

            precomputedResults.put(color, beautyValues);
        }

        return precomputedResults;
    }
}