2894: 子数组排序
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
Monocarp有个长度为n的数组a ，他打算选两个整数l和r，将子数组a[l...r]排序为非降序，进而得到一个新数组a′。比如， a=[6，7，3，4，4，6，5]， Monocarp取l=2，r=5，则a'=[6，3，4，4，7，6，5]。现在，给你数组a和a′，请找出Monocarp选择的l和r，使得子序列长度最长，输出子序列最长的长度。
输入
第一行是测试用例数 t ( 1≤t≤10^4 ) 。随后是 t组测试用例的描述。
每组测试用例的第1行是一个整数 n ( 2≤n≤2⋅10^5 );
第二行是 n 个整数 a1,a2,…,an ( 1≤ai≤n );
第三行是 n 个整数 a1′,a2′,…,an′ ( 1≤ai′≤n ).
保证所有测试用例中的 n 的总和不超过 2⋅10^5，且 a′ 可由 a 得到， a′≠a。
每组测试用例的第1行是一个整数 n ( 2≤n≤2⋅10^5 );
第二行是 n 个整数 a1,a2,…,an ( 1≤ai≤n );
第三行是 n 个整数 a1′,a2′,…,an′ ( 1≤ai′≤n ).
保证所有测试用例中的 n 的总和不超过 2⋅10^5，且 a′ 可由 a 得到， a′≠a。
输出
对于每组样例，输出子序列最长的长度。
样例输入 复制
3
7
6 7 3 4 4 6 5
6 3 4 4 7 6 5
3
1 2 1
1 1 2
3
2 2 1
2 1 2样例输出 复制
4
3
2