Maximize Segment Diversity

You are a market analyst tasked with studying customer purchase data to identify periods of high product diversity. You are given a sequence of purchases, A, where each element is a product_id.

To analyze this data, you must split the entire sequence into exactly K continuous, non-empty "time windows" (segments).

The "diversity score" of a single time window is defined as the number of unique product_ids it contains. Your goal is to find a way to split the purchase history into K windows such that the sum of the diversity scores of all windows is maximized.

Input Format:

The first line contains two space-separated integers, N (the number of purchases) and K (the number of windows).

The second line contains N space-separated integers, representing the sequence of product_ids.

Output Format:

The output should be a single integer representing the maximum possible total diversity score.

Note:

Each of the K segments must be a non-empty, contiguous block of the original array.

The K segments, when placed together, must form the complete original array.