Description

You are given a sequence $a$ of length $n$.

You can increase a number in the sequence by $1$, which is called one operation.

You need to process $q$ queries.

For each query, find the minimum number of operations needed so that $a$ can be turned into a sequence $a'$, where $x$ is a mode of $a'$.

Note: A sequence may have multiple modes.

Input Format

The first line contains two integers $n,q$.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$.

The next $q$ lines each contain one integer $x$.

Output Format

For each query, if there is no solution output -1, otherwise output the minimum number of operations.

Print each answer on a separate line.

6 2
1 1 1 3 3 3
2
10

3
13

Hint

[Sample 1 Explanation]

• When $x=2$, one feasible plan is $a'=[1,2,2,3,3,4]$.
• When $x=10$, one feasible plan is $a'=[1,2,3,4,5,10]$.

[Constraints and Notes]

This problem uses bundled tests.

• Subtask 1 (5 points): $n=3$.
• Subtask 2 (5 points): all $a_i$ are equal, time limit is 2000 ms.
• Subtask 3 (5 points): $n\le 10$, $q\le 10^3$.
• Subtask 4 (15 points): $n\le 100$, $q\le 10^4$.
• Subtask 5 (15 points): $n\le 10^3$.
• Subtask 6 (15 points): $q\le 10^3$.
• Subtask 7 (40 points): time limit is 2000 ms.

For $100\%$ of the testdata, $1\le n,q\le 10^5$, $1\le a_i,x\le 10^9$.

Translated by ChatGPT 5