由 ChatGPT 4o 生成的图像。
Mayaw在法塔安村一家著名的Epah(台湾原住民小米酒;Epah是台湾原住民小米酒的Pangcah术语,以台湾最大原住民Pangcah人的语言命名)工作。为了展示其藏品的深度,酒吧设有两排酒架,每排酒架均可准确放置 $$$n$$$ 瓶。货架后排已经放置了 $$$n$$$ 瓶,其中左起第 $$$i$$$ 瓶的高度为 $$$a_i$$$。酒吧老板还有另外 $$$n$$$ 瓶,其高度不同 $$$b_1、\ldots、b_n$$$,他希望 Mayaw 将其放在第一排。为了保证架子上的所有瓶子都能被看见,店主要求后排的每个瓶子都不能被前面的瓶子挡住。也就是说,如果将高度为 $$$h$$$ 的瓶子放在第一行中第 $$$i$$$ 个位置(从左起),则 $$$h$$$ 必须小于 $$$a_i$$$。然而,并非所有这样的安排都对业主有利。为了向附近的马西山致敬,他还要求前排的瓶子必须呈山形。特别是,当从左到右列出时,瓶子的高度应形成先(非严格)增加然后(非严格)减少的序列。
不幸的是,有时无法实现业主的要求。这就是为什么 Mayaw 还可以通过移除高度为 $$$1$$$ 的瓶盖来稍微降低瓶子的高度。换句话说,取下瓶盖后,瓶子的高度正好减少$$$1$$$。当然,将瓶内的Epa暴露在露天会损害其质量,因此希望尽可能少地去除瓶盖。
你能帮助 Mayaw 确定需要移除的最少瓶盖数量,以便他能够按照主人要求的方式排列瓶子吗?请注意,后排瓶子的位置是固定的,不允许 Mayaw 修改它们。
输入
第一行包含一个整数 $$$n$$$,表示每行中的瓶子数量。第二行包含$$$n$$$整数$$$a_1,\ldots,a_n$$$,后排瓶子的高度。第三行包含 $$$n$$$ 不同的整数 $$$b_1, \ldots, b_n$$$,前排瓶子的高度。
- $$$1 \leq n \leq 5 \times 10^5$$$
- $$$1 \leq a_i, b_i \leq 10^9$$$
- 所有 $$$b_i$$$ 都是不同的。
输出
输出需要移除的最少瓶盖数量,以便 Mayaw 可以按照所需的方式排列瓶子。如果无法实现这一点(无论移除了多少个大写字母),则输出 -1。
示例
输入 #1
5 2 4 6 5 4 1 2 3 4 5
输出 #1
0
输入 #2
5 2 3 6 5 4 1 2 3 4 5
输出 #2
0
输入 #3
5 6 2 6 6 6 1 2 3 4 5
输出 #3
1
输入#4
5 7 2 7 7 7 1 3 4 5 6
输出#4
-1
输入 #5
10 18 20 16 18 16 10 13 6 4 10 19 10 9 15 4 16 6 12 3 17
输出 #5
4