Se te da un arreglo h_1, h_2, \ldots, h_n de números enteros. Divídelo en dos subsecuencias, es decir, asigna cada elemento a exactamente una de las dos subsecuencias (cualquiera de ellas puede estar vacía), de modo que:
la primera subsecuencia sea no decreciente: si está formada por los elementos con índices i_1 < i_2 < \ldots < i_k, entonces h_{i_1} \le h_{i_2} \le \ldots \le h_{i_k};
la segunda subsecuencia sea no creciente: si está formada por los elementos con índices j_1 < j_2 < \ldots < j_l, entonces h_{j_1} \ge h_{j_2} \ge \ldots \ge h_{j_l}.
Determina si existe tal división.
La primera línea contiene un único entero (1 \le t \le 10^4) — la cantidad de casos de prueba.
Cada caso de prueba consta de dos líneas. La primera línea contiene un entero (1 \le n \le 10^6) — la longitud del arreglo. La segunda línea contiene enteros h_1, h_2, \ldots, h_n (0 \le h_i \le 10^9).
La suma de sobre todos los casos de prueba no supera 10^6.
Para cada caso de prueba, imprime una línea con YES si existe una división adecuada, y NO en caso contrario.
Las palabras YES y NO se pueden imprimir en cualquier combinación de mayúsculas y minúsculas.
Ejemplo 1
En el primer caso de prueba h = [3, 5, 5, 2, 6, 1], y existe una división adecuada, por lo que la respuesta es YES.
Por ejemplo, la subsecuencia no decreciente puede ser , y la subsecuencia no creciente 5, 5, 2, 1.
Otra división adecuada: la subsecuencia no decreciente es 3, 5, 5, 6, y la no creciente es .
La figura muestra la primera de estas divisiones: la subsecuencia no decreciente es oscura (línea continua), y la no creciente es clara (línea discontinua).
En el segundo caso de prueba h = [2, 1, 4, 3]. Supongamos que el elemento pertenece a la subsecuencia no creciente.
Entonces los elementos anteriores y menores y no pueden pertenecer a ella, así que ambos pertenecen a la subsecuencia no decreciente, pero esa subsecuencia no puede contener seguido de .
Por lo tanto, el elemento pertenece a la subsecuencia no decreciente, y entonces el elemento posterior y menor pertenece a la no creciente.
Ahora los elementos y son anteriores y menores que , por lo que no pueden pertenecer a la subsecuencia no creciente, y de nuevo ambos tendrían que pertenecer a la no decreciente, lo cual es imposible.
Por consiguiente, la respuesta es NO.
En el tercer caso de prueba todos los elementos pueden pertenecer a una sola subsecuencia, y la otra queda vacía.
En el quinto caso de prueba la subsecuencia no creciente es , y la subsecuencia no decreciente es .