思路：贪心模拟

贪心的根据当前元素与队列两端元素的大小关系，选择小的来插入，以确保队列单调不降。如果无法满足条件，则返回 "NO"。

代码

java

import java.util.ArrayDeque;
import java.util.Deque;

题目内容

小苯有一个长度为$n$的数组$a_1,a_2,...,a_n$，和一个初始为空的双端队列$q$。在这里，双端队列是一种数据结构，其两端都可以放入元素，你可以参考样例解释获得更形象的说明。

他想要将数组中的元素从左到右依次取出、放入$q$中。是否存在一种放入方式，使得全部数字放入后，$q$中的元素从左到右单调不降。

单调不降是指对于$q$中从左到右的第$i$个元素$q$，如果$q_{i+1}$存在，那么$q_i≤q_{i+1}$。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T$($1≤T≤10^4$)代表数据组数，每组 测试数据描述如下: 第一行输入一个正整数$n$($1≤n≤2×10^5$)代表数组中的元素数量。

第二行输入$n$个整数$a_1，a_2...,a_n$($1≤a_i≤10^9$)代表数组中的元素。

除此之外，保证所有的$n$之和不超过$2×10^5$。

输出描述

对于每一组测试数据，如果存在这样的放入方式，在一行上输出$YES$，否则，直接输出$NO$。

样例1

输入

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]$。 注意，上述列出的只是其中一种合法的放入方式，并不代表唯一解。