← Back to Problems
English

Language

Hard Sorting Problem

by _junick · UCPC 2026 Pre

Problem information
Time limit Memory limit Published
1000 ms 1024 MB

Statement

An integer sequence \(A\) of length \(N\) is given. The sequence is partitioned into \(K\) non-overlapping segments, where the length of the \(i\)-th segment from the left is \(l_i\). You may perform the following operation any number of times.

  • Choose one of the \(K\) segments.
  • Let \(m\) and \(M\) be the minimum and maximum values among the elements in the chosen segment immediately before the operation. Replace every element in that segment with an arbitrary integer between \(m\) and \(M\), inclusive.

The goal is to make the sequence non-decreasing.

After all operations are performed, let the resulting sequence be \(B\). For a value \(x\), let \(c_A(x)\) be the number of times \(x\) appears in the initial sequence \(A\), and let \(c_B(x)\) be the number of times \(x\) appears in the resulting sequence \(B\). The cost of \(B\) is defined as follows:

\[\sum_x \max(0, c_B(x)-c_A(x)).\]

Determine whether it is possible to make the sequence non-decreasing, and output the minimum cost of such a final sequence if possible.

Input

The first line contains two integers \(N\) and \(K\), separated by a space. (\(1 \le K \le N \le 200\,000\))

The second line contains \(N\) integers \(A_1,A_2,\cdots,A_N\), separated by spaces. (\(0 \le A_i \le 10^9\))

The third line contains \(K\) integers \(l_1,l_2,\cdots,l_K\), separated by spaces. (\(1 \le l_i \le N\); \(\sum_{i=1}^K l_i=N\)) These indicate that the sequence is partitioned into \(K\) segments of lengths \(l_1,l_2,\cdots,l_K\), from left to right.

Output

If it is possible to make the sequence non-decreasing, output the minimum possible cost. Otherwise, output \(-1\).

Examples

Sample input 1

5 3
3 1 4 2 5
2 1 2

Sample output 1

1

In the example above, the sequence \(A\) is partitioned into the segments \([1,2]\), \([3,3]\), and \([4,5]\).

It is possible to obtain a non-decreasing sequence \([1,3,4,5,5]\). For the initial sequence \(A=[3,1,4,2,5]\) and the final sequence \(B=[1,3,4,5,5]\), the cost is calculated as follows.

\(x\) 1 2 3 4 5
\(c_A(x)\) 1 1 1 1 1
\(c_B(x)\) 1 0 1 1 2

Thus, the cost is \(0+0+0+0+1=1\), and it can be proven that no other non-decreasing final sequence has a smaller cost.

Sample input 2

4 4
3 1 2 4
1 1 1 1

Sample output 2

-1

Since every segment has length of \(1\), it is impossible to change the sequence. Therefore, the final sequence must be \([3,1,2,4]\), which is not non-decreasing.