¿Conoces este problema?#13112

¿Conoces este problema?

1 segundo
256 megabytes

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:

Determina si existe tal división.

Entrada

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.

Salida

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.

Ejemplos

Ejemplo 1

Loading
Loading

Nota

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 .