手玩样例，我们可以发现一个取数字的时候最优的解法：即:假设数组\(b\)中\(j\)之前的位置的花花都已经取到了，并且在\(a\)数组当中遍历到了下标为\(i\)的位置，且满足\(a_i \geq b_j\)，那么当前的这个第\(i\)朵花一定要拿，否则不是最优。
为什么呢？我们假设当前这个第\(i\)朵花不取，而是取了\(i\)之后的一朵花\(k\)，那么\([i,k-1]\)位置内的花都无法在\(b\)数组中的\(j\)位置之后被取到，因为在\(b\)数组中的花必须顺序取完。所以说\(j\)位置之后的花在这种情况下只能取到\([k+1,n]\)位置的花。但是如果取了第\(i\)朵花，\([i+1,k]\)位置的花就都有机会被\(b\)数组中\(j\)位置之后取到，显然\(j\)位置之后能取到的花更多了。
那么这道题中我们可以在\(a\)中额外添加一朵美丽值为\(k\)花，然后求出能满足\(b\)数组的要求下让\(k\)最小，那么如果\(b\)数组的要求都能满足，这个\(k\)一定是\(b\)要求的某一个之中的值，可以认为是某一个要求无法满足，然后我加了这朵花让它满足要求。那么我们就可以枚举\(b\)之中的每一个要求，看看去掉这个要求之后左右两部分是否都可以取完。
如何判断左右两部分都可以取完？从最开始的解法中我们已经知道了从左往右取一定是满足要求就取，左半部分恰好取完在\(a\)中的下标可以求出来，记为\(p_{j-1}\)；同理我们也可以找到在\(a\)数组中从右向左取完\(b\)数组中\(j+1\)位置及其右侧时的下标，记为\(s_{j+1}\)这样可以保证左半部分的端点最靠左，右半部分的端点最靠右，如果有\(p_{j-1}<s_{j+1}\)，就说明去掉\(b_j\)之后左右部分都可以在原数组中取完。我们还需要特判一下，如果是去掉开头\(b_1\)，那么需要判断\(s_2>=1\)是否成立，如果是去掉结尾\(b_m\)，我们需要判断\(p_{m-1}<=n\)是否成立。如果说没有符合题意的\(b_j\)，就输出\(-1\)。
代码
#include <bits/stdc++.h>
using namespace std;
/**/
#define ll long long
void sol() {int n,m;cin>>n>>m;vector<ll> a(n+1),b(m+1),p(m+1,1e18),s(m+1,-1e18);for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>b[i];for(int i=1,j=1;i<=n&&j<=m;i++){if(a[i]>=b[j]){p[j++]=i;}}for(int i=n,j=m;i>=1&&j>=1;i--){if(a[i]>=b[j]){s[j--]=i;}}ll ans=1e18;if(s[2]>=1) ans=min(ans,b[1]);if(p[m-1]<=n) ans=min(ans,b[m]);for(int i=2;i<=m-1;i++){if(p[i-1]<s[i+1]) ans=min(ans,b[i]);}if(p[m]<=n) ans=0;if(ans==1e18) ans=-1;cout<<ans<<'\n';
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {sol();}return 0;
}