J. Bottle Arrangement
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Image generated by ChatGPT 4o.

Mayaw works in a renowned Epah (aboriginal Taiwanese millet wine; Epah is the Pangcah term for aboriginal Taiwanese millet wine, named in the language of the Pangcah people, the largest Indigenous group in Taiwan) bar in the Fata'an Village. To showcase the depth of its collections, the bar has a two-row wine rack where each row can fit exactly $$$n$$$ bottles. There are already $$$n$$$ bottles placed on the back row of the rack, where the $$$i$$$-th bottle from left has height $$$a_i$$$. The owner of the bar has another $$$n$$$ bottles with distinct heights $$$b_1, \ldots, b_n$$$ that he would like Mayaw to put on the first row. To ensure that all bottles on the rack are visible, the owner requires that each bottle on the back row should not be blocked by the one put in front of it. That is, if a bottle of height $$$h$$$ is put on the $$$i$$$-th spot (from left) in the first row, then $$$h$$$ must be less than $$$a_i$$$. However, not all such arrangements are good for the owner. To pay tributes to the Maxi Mountain nearby, he additionally demands that the bottles in the front row should display a mountain-like shape. In particular, the heights of the bottles, when listing from left to right, should form a sequence that is first (non-strictly) increasing and then (non-strictly) decreasing.

Unfortunately, sometimes it is impossible to achieve owner's requirements. That is why Mayaw is also allowed to slightly reduce a bottle's height by removing its cap that has a height of $$$1$$$. In other words, after the removal of the cap, the height of the bottle decreases by exactly $$$1$$$. Of course, exposing the Epah inside the bottle to the open air is detrimental to its quality, and therefore it is desirable to remove as few bottle caps as possible.

Can you help Mayaw determine the minimum number of caps needed to be removed so that he can arrange the bottles in a way that satisfies the owner's requirements? Note that the positions of the bottles in the back row are fixed and Mayaw is not allowed to modify them.

Input

The first line contains an integer $$$n$$$ which represents the number of bottles in each row. The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$, the height of the bottles in the back row. The third line contains $$$n$$$ distinct integers $$$b_1, \ldots, b_n$$$, the height of the bottles in the front row.

  • $$$1 \leq n \leq 5 \times 10^5$$$
  • $$$1 \leq a_i, b_i \leq 10^9$$$
  • All $$$b_i$$$'s are distinct.
Output

Output the minimum number of bottle caps needed to be removed so that Mayaw can arrange the bottles in the desired way. If it is impossible to achieve that (regardless of the number of caps removed), output -1 instead.

Examples
Input
5
2 4 6 5 4
1 2 3 4 5
Output
0
Input
5
2 3 6 5 4
1 2 3 4 5
Output
0
Input
5
6 2 6 6 6
1 2 3 4 5
Output
1
Input
5
7 2 7 7 7
1 3 4 5 6
Output
-1
Input
10
18 20 16 18 16 10 13 6 4 10
19 10 9 15 4 16 6 12 3 17
Output
4