Size tam sayılardan oluşan bir h_1, h_2, \ldots, h_n dizisi veriliyor. Bu diziyi iki alt diziye ayırın, yani her elemanı iki alt diziden tam olarak birine atayın (bunlardan herhangi biri boş olabilir), öyle ki:
birinci alt dizi azalmayan olsun: eğer i_1 < i_2 < \ldots < i_k indisli elemanlardan oluşuyorsa, o zaman h_{i_1} \le h_{i_2} \le \ldots \le h_{i_k};
ikinci alt dizi artmayan olsun: eğer j_1 < j_2 < \ldots < j_l indisli elemanlardan oluşuyorsa, o zaman h_{j_1} \ge h_{j_2} \ge \ldots \ge h_{j_l}.
Böyle bir ayrımın var olup olmadığını belirleyin.
İlk satırda bir tam sayı (1 \le t \le 10^4) — test durumlarının sayısı verilir.
Her test durumu iki satırdan oluşur. İlk satırda bir tam sayı (1 \le n \le 10^6) — dizinin uzunluğu verilir. İkinci satırda tam sayı h_1, h_2, \ldots, h_n (0 \le h_i \le 10^9) verilir.
Tüm test durumları üzerinden değerlerinin toplamı 10^6 değerini aşmaz.
Her test durumu için, uygun bir ayrım varsa YES, aksi hâlde NO yazdırın.
YES ve NO kelimeleri büyük veya küçük harflerle yazdırılabilir.
Örnek 1
Birinci test durumunda h = [3, 5, 5, 2, 6, 1] ve uygun bir ayrım vardır, bu yüzden cevap YES olur.
Örneğin, azalmayan alt dizi , artmayan alt dizi ise 5, 5, 2, 1 olabilir.
Uygun başka bir ayrım: azalmayan alt dizi 3, 5, 5, 6, artmayan alt dizi ise .
Şekilde bu ayrımlardan birincisi gösterilmiştir: azalmayan alt dizi koyu (düz çizgi), artmayan alt dizi ise açık (kesikli çizgi) renktedir.
İkinci test durumunda h = [2, 1, 4, 3]. elemanının artmayan alt diziye ait olduğunu varsayalım.
O hâlde ondan önce gelen ve ondan küçük olan ve elemanları bu alt diziye ait olamaz, dolayısıyla ikisi de azalmayan alt diziye aittir; ancak bu alt dizide 'den sonra gelemez.
Öyleyse elemanı azalmayan alt diziye aittir ve o zaman ondan sonra gelen ve ondan küçük olan elemanı artmayan alt diziye aittir.
Şimdi ve elemanları 'ten önce gelir ve ondan küçüktür, bu yüzden artmayan alt diziye ait olamazlar ve yine ikisi de azalmayan alt diziye ait olmak zorunda kalır, bu ise mümkün değildir.
Bu nedenle cevap NO olur.
Üçüncü test durumunda tüm elemanlar tek bir alt diziye ait olabilir, diğeri ise boş kalır.
Beşinci test durumunda artmayan alt dizi , azalmayan alt dizi ise 'tür.