时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
给定一个长度为

的序列,问它是否存在一个子序列,使得这个子序列是一个

的排列。
某个序列的
子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置(在前或在后)而形成的新序列。
一个

的排列是一个长度为

的整数序列,其中包含了从

到

的每个数字,每个数字仅出现一次。例如,
%20%2C%20(4%2C%E2%80%893%2C%E2%80%895%2C%E2%80%891%2C%E2%80%892)%20%2C(3%2C%E2%80%892%2C%E2%80%891))
是排列,而
%20%2C%20(4%2C%E2%80%893%2C%E2%80%891)%20%2C%20(2%2C%E2%80%893%2C%E2%80%894))
不是。
输入描述:
第一行包含一个
,表示测试用例组数。
每个测试用例第一行包含两个整数
。
第二行包含
个用空格分隔的整数
,表示给定的序列。
输出描述:
对于每个测试用例,假如给定序列中存在一个子序列,使得这个子序列是一个长度为
的排列,输出
,否则输出
。
示例1
输入
复制
5
5 4
1 2 4 5 3
5 6
1 2 3 4 100
5 5
1 2 3 5 6
3 2
1 3 3
1 1
1
说明
对于第一组测试用例,输入的序列包含一个子序列 (1,2,4,3),是一个 4 的排列。
对于第二组测试用例,输入的序列没有一个子序列是 6 的排列。