🌳 题目描述：

题目内容

小羊有一个长度为 n 的数组 a1,a2,...,an 和一个初始为空的双端队列 q。在这里，双端队列是一种数据结构，其两端都可以放入元素，你可以参考样例解释获得更形象的说明。他想要将数组中的元素从左到右依次取出、放入 q中。是否存在一种放入方式，使得全部数字放入后，q 中的元素从左到右单调不降。单调不降是指对于 q 中从左到右的第 i 个元素 q，如果 q(i + 1) 存在，那么 qi ≤ q(i + 1)。

输入描述

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

第二行输入 n 个整数 a1，a2...,an (1 ≤ ai ≤$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]，能构成从左到右单调不降的序列，返回 YES。 对于第二组测试数据，[]→[1]→[1,1]→[1,1,1]，能构成从左到右单调不降的序列，返回 YES。 对于第三组测试数据，[]→[1]→[1,3], 接下来的 2 无论是放在左边还是右边，都无法构成从左到右单调不降的序列，返回 NO。

🕵🏽 面试评估：

这道题主要考察候选人是否具备扎实的基础知识和清晰的思考过程，是否了解双端队列，能否通过题目进行模拟操作解决问题。

🧗难度系数：

⭐️ ⭐️ ⭐️

提示

思路分析，题解，代码，复杂度分析仅对算法/后端训练营用户开放