Problem Description

In a positive integer array or subarray, for each distinct number, multiply the number by its number of occurrences; this is called its superposition value. A “subarray” means a part of an array made up of consecutive elements. For example, in the array $[4, 5, 2, 3, 4, 2, 2]$, the superposition value of $5$ is $5\times1=5$, the superposition value of $4$ is $4\times2=8$, the superposition value of $3$ is $3\times1=3$, and the superposition value of $2$ is $2\times3=6$.

Given a positive integer array of length $n$ and a positive integer $k$, this problem asks for the maximum superposition value in every subarray of length $k$. There are $n-k+1$ subarrays of length $k$ in total. Output the sum of these $n-k+1$ maximum superposition values.

For example, the input array is $[4, 5, 2, 3, 4, 2, 2, 5]$, with $n=8$ and $k=5$. The maximum superposition values of each subarray are:

• For $[4, 5, 2, 3, 4]$, the maximum superposition value is $4\times2=8$.
• For $[5, 2, 3, 4, 2]$, the maximum superposition value is $5\times1=5$.
• For $[2, 3, 4, 2, 2]$, the maximum superposition value is $2\times3=6$.
• For $[3, 4, 2, 2, 5]$, the maximum superposition value is $5\times1=5$.

The sum of all maximum superposition values is $8+5+6+5=24$.

Input Format

• $n$ is the length of the array.
• $k$ is the required subarray length.
• $c_i$ is the $i$-th positive integer in the array.

Output Format

$X$

• $X$ is the sum of all maximum superposition values.

8 5
4 5 2 3 4 2 2 5

24

Hint

Constraints

• $1 \le n\le 10^5$.
• $1 \le k \le n$.
• $1 \le c_i < 2^{31}$.

Scoring

This problem has three subtasks with the following constraints.
Each subtask may contain one or more testdata files. You will get the score for a subtask only if you answer all testdata in that subtask correctly.

Translated by ChatGPT 5