小苯有一个长度为n的数组a1,a2,...,an,和一个初始为空的双端队列q。在这里,双端队列是一种数据结构,其两端都可以放入元素,你可以参考样例解释获得更形象的说明。
他想要将数组中的元素从左到右依次取出、放入q中。是否存在一种放入方式,使得全部数字放入后,q中的元素从左到右单调不降。
单调不降是指对于q中从左到右的第i个元素q,如果qi+1存在,那么qi≤qi+1。
每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤104)代表数据组数,每组 测试数据描述如下: 第一行输入一个正整数n(1≤n≤2×105)代表数组中的元素数量。
第二行输入n个整数a1,a2...,an(1≤ai≤109)代表数组中的元素。
除此之外,保证所有的n之和不超过2×105。
对于每一组测试数据,如果存在这样的放入方式,在一行上输出YES,否则,直接输出NO。
输入
3
4
2 3 1 4
3
1 1 1
3
1 3 2
输出
YES
YES
NO
对于第一组测试数据,[]→[2]→[2,3]→[1,2,3]→[1,2,3,4]。 对于第二组测试数据,[]→[1]→[1,1]→[1,1,1]。 注意,上述列出的只是其中一种合法的放入方式,并不代表唯一解。
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.