### Solution : [problem:2237B]↵
↵
#### Hint 01↵
↵
We are given that the final array $b$ is strictly increasing ($b_1 < b_2 < \dots < b_n$). We construct this final array from left to right. Since we can only **add** ducks, an initial pile $a_j$ can be transformed into a target pile $b_i$ if and only if $a_j \le b_i$.↵
↵
#### Hint 02↵
↵
If we decide which elements of $a$ map to which elements of $b$, the number of adjacent swaps required to reorder them into their final positions is exactly the number of **inversions** created by our choice.↵
↵
---↵
↵
###SolutionGreedy Approach↵
↵
Since $b$ is strictly increasing, i.e. ($b_1 < b_2 < \cdots < b_n$), the condition $a_j \le b_i$ becomes easier to satisfy as $i$ increases. Therefore, it is optimalbest to process the elements of $b$ from left to right. ↵
↵
For each $b_i$, we choose the **leftmost unused** position $j$ such that $a_j \le b_i$. This greedy choiceis optimal because selectworks perfectly because:↵
↵
1. Choosing an earlier valid elementcan never make future matchings harder: any element appearing later in $a$ remains available for the larger values of $b$ that will be processed afterwards. Furthermore, among all feasible choices, tleaves later elements available for the larger values of $b$ coming up next.↵
2. Taking the leftmostoneavailable element minimizes the distance the chosen element must travel, which directly helps minimize the number of adjacent sit has to travel, which keeps the number of swaps as small as possible.↵
↵
### Counting Swaps.↵
↵
Suppose the element chosen for $b_i$ islocated at position $j$. To move it into its required positioncorrect spot, it must swap passt every still-unused element located to its left. Positionelement to its left that hasn't been used yet. Elements that havare already been matched do non't countribute, sinc because they have effectivelalready been removed from the sequence. Thereforeout of the way.↵
↵
So, the number of swapscontributed byneeded for position $j$ is exactsimply the number of **unmatched positions before it, namely↵
$$↵
|{,**:↵
↵
$$|\{k < j \mid k \text{ has not been matched yet},\}|.↵
$$↵
If we maintain all currently unused positions ↵
While this can be optimized using a **Fenwick Tree, this value can be obtained as the prefix sum on the range $[1, j-1]$. After matching position $j$, we remove it from the data structure** (Binary Indexed Tree) to query prefix sums in $O(\log n)$ time, the constraints here allow us to just use a simple loop to count unmatched elements in $O(n)$ time per step. Summing these contributions over all matched positions yields the minimum number of adjacent swaps required.↵
### Implementation↵
↵
↵
~~~~~unts up for all elements gives us our final answer. If we ever find a $b_i$ that cannot match with any available $a_j$, it's impossible, so we output `-1`.↵
↵
```cpp↵
int n, ans = 0;↵
cin >> n;↵
vector<int> a(n), b(n), seen(n + 1);↵
↵
for (int& it : a) cin >> it;↵
for (int& it : b) cin >> it;↵
↵
for (int i = 0; i < n; ++i) {↵
bool ok = false;↵
for (int j = 0; j < n; ++j) {↵
if (a[j] <= b[i] && !seen[j]) {↵
ok = true;↵
seen[j] = 1;↵
break;↵
}↵
if (!seen[j])++ans;{↵
++ans;↵
}↵
}↵
if (!ok) {↵
cout << -1 << endl;↵
return;↵
}↵
}↵
↵
cout << ans << endl;↵
~~~~~↵
↵
```↵
↵
### Complexity Analysis↵
↵
* **Time Complexity:** $\mathcal{O}(n^2)$ per test case. Since $\sum n \le 2000$, an $n^2$operationsapproach easily runs well within the 1.5-second time limit.↵
* **Space Complexity:** $\mathcal{O}(n)$ to store the arrays and the tracking (`seen`) array.
↵
---↵
↵
###
↵
Since $b$ is strictly increasing
↵
For each $b_i$, we choose the **leftmost unused** position $j$ such that $a_j \le b_i$. This greedy choice
↵
1. Choosing an earlier valid element
2. Taking the leftmost
↵
### Counting Swaps
↵
Suppose the element chosen for $b_i$ is
↵
So, the number of swaps
$$↵
|{,
↵
$$|\{k < j \mid k \text{ has not been matched yet}
While this can be optimized using a **Fenwick Tree
### Implementation↵
↵
↵
~~~~~
↵
```cpp↵
int n, ans = 0;↵
for (int& it : a) cin >> it;↵
↵
bool ok = false;↵
for (int j = 0; j < n; ++j) {↵
if (a[j] <= b[i] && !seen[j]) {↵
ok = true;↵
seen[j] = 1;↵
break;↵
}↵
if (!seen[j])
++ans;↵
}↵
}↵
if (!ok) {↵
cout << -1 << endl;↵
return;↵
}↵
↵
```↵
### Complexity Analysis↵
↵
* **Time Complexity:** $\mathcal{O}(n^2)$ per test case. Since $\sum n \le 2000$, an $n^2$
* **Space Complexity:** $\mathcal{O}(n)$ to store the arrays and the tracking (`seen`) array.



