Let $a$ be a sorted array of integers of size $n$. We'll define an insert operation on an integer $k$ as follows:
$\quad \quad$ - The array first becomes $\{1, 1, 1, 3\}$, and $k$ becomes $2$, then the insert operation is repeated.
$\quad \quad$ - The array becomes $\{1, 1, 1, 2\}$ and $k$ becomes $3$, then the insert operation is repeated once more.
$\quad \quad$ - The array becomes $\{1, 1, 1, 2, 3\}$.
Given a sorted array $a$ of size $n$, and a sequence of integers $k$ of size $m$, find the number of replacement operations required to insert all integers into $a$, in the order $k_1,\space k_2,\space ...\space ,\space k_m$.
The first line consists of two integers, $n$ and $m$ ($1 \leq n, m \leq 10^4$), the number of elements in the array and the number of elements that need to be inserted into the array, respectively.
The next line contains $n$ space-separated integers $a_1,\space a_2,\space ...\space ,\space a_n,\space 1 \leq a_i \leq 10^3$, which represent the original array.
The last line of input contains $m$ space-separated integers $k_1,\space k_2,\space ...\space ,\space k_m,\space 1 \leq k_i \leq 10^3$, which represent the sequence of numbers that need to be inserted into the array.
Output a single integer $r$, the number of replacement operations required to insert all $m$ elements into the array in the order in which they're given.
In the first test case, both the $5$ and $6$ are appended to the end of the array, so no replacements are required.
In the second test case, one replacement is required to insert the $2$, and two replacements are then required to insert the $1$.
Input | Output |
---|---|
4 2 1 1 2 3 5 6 Copy
|
0 Copy
|
4 2 1 1 2 3 2 1 Copy
|
3 Copy
|