P3377.第2题-数组长度排列
题目内容
给定一个长度为 n 的整数数组 a 。你可以对 a 进行若干次下面的操作(可以不操作):
- 选择一个下标 1≦i≦n，并将 ai 更新为⌊2ai⌋。在这里，⌊x⌋ 意味着对 x 下取整。
小欧想知道，是否存在一个操作序列，使得在所有操作后数组 a 为一个排列?
【名词解释】
长度为 n 的排列是由 1,2,...,n 这 n 个整数、按任意顺序组成的数组(每个整数均恰好出现一次)。例如，{2,3,1,5,4} 是一个长度为 5 的排列，而 {1,2,2} 和 {1,3,4} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤104) 代表数据组数，每组测试数据描述如下：
第一行包含一个整数 n(1≤n≤2×105) ，表示数组 a 的长度。
第二行包含长度为 n 个整数，0≤ai≤109
除此之外，保证单个测试文件的 n 之和不超过 2×105 。
输出描述
输出 T 行，其中第 i 行为第 i 组测试数据的答案。对于每一组测试数据，如果答案存在，在一行上输出 YES ; 否则直接输出 NO 。您可以以任何大小写形式输出答案。例如，字符串 yEs、yes 和 Yes 都将被视为肯定的回答。
样例1
输入
5
3
1 2 4
3
1 2 6
1
1
2
1 536870911
5
25752 3010 1188 126 270
输出
NO
YES
YES
NO
YES
说明
对于第 2 组测试数据，我们可以对 a3 进行一次操作，数组 a 变为 {1,2,3} ，是长度为 3 的排列。
