NCPC
题号:NC306094
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 1024 M,其他语言2048 M
64bit IO Format: %lld

题目描述

NCPC
欢迎大家参加NCPC!
\hspace{15pt}Bingbong 正在负责 NCPC (Nowcoder Collegiate Pizza Contest, NCPC) - 牛客大学生披萨大赛的准备工作,现在有 n 个参赛选手,编号为 1\sim n,编号为 i 的选手制作的 Pizza 的美味值为 a_i。对于每轮比赛,Bingbong 会选取当前场上任意两个未被淘汰的选手 i,j\left(i\neq j\right) 进行对决,具体规则如下:

\hspace{23pt}\bullet\,a_i\neq a_j ,则制作 Pizza 的美味值较低的选手淘汰,否则两位选手都淘汰。直到只剩下一名选手时,该选手获胜,若没有选手剩下,则全部淘汰。

\hspace{15pt}现在你需要帮助 Bingbong 判断,是否存在一种对决安排,使得选手 i\left(1\leq i\leq n\right) 最终成为唯一剩下的选手(即获得最终胜利)。若存在,输出 \texttt{1};否则输出 \texttt{0}

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 10^4\right) 代表数据组数,每组测试数据描述如下:

\hspace{15pt}第一行输入一个整数 n\left(1\leq n\leq 2\times 10^5\right),表示参赛选手的数量。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n\left(1\leq a_i\leq 10^9\right),表示选手制作的 Pizza 对应的美味值。

\hspace{15pt}除此之外,保证单个测试文件的 n 之和不超过 2\times 10^5

输出描述:

\hspace{15pt}对于每一组测试数据,新起一行输出一个长度为 n、仅由字符 \texttt{0}\texttt{1} 构成的字符串 s,其中,第 i 个字符 s_i\texttt{1},当且仅当选手 i 最终成为唯一剩下的选手(即获得最终胜利)。
示例1

输入

复制
2
4
2 2 2 2
6
1 1 4 5 1 4

输出

复制
0000
000100