Hard Sorting Problem

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.

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.

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