Bu məsələni tanıyırsınız?#13112

Bu məsələni tanıyırsınız?

1 saniyə
256 meqabayt

Sizə tam ədədlərdən ibarət h_1, h_2, \ldots, h_n massivi verilib. Onu iki alt ardıcıllığa bölün, yəni hər elementi iki alt ardıcıllıqdan dəqiq birinə aid edin (onlardan istənilən biri boş ola bilər), belə ki:

Belə bölgünün mövcud olub-olmadığını müəyyən edin.

Giriş

Birinci sətirdə bir tam ədəd (1 \le t \le 10^4) — test hallarının sayı verilir.

Hər test halı iki sətirdən ibarətdir. Birinci sətirdə tam ədəd (1 \le n \le 10^6) — massivin uzunluğu verilir. İkinci sətirdə tam ədəd h_1, h_2, \ldots, h_n (0 \le h_i \le 10^9) verilir.

Bütün test halları üzrə qiymətlərinin cəmi 10^6-dan çox deyil.

Çıxış

Hər test halı üçün uyğun bölgü mövcuddursa YES, əks halda NO sətrini çıxarın.

YES və NO sözlərini istənilən registrdə çıxarmaq olar.

Nümunələr

Nümunə 1

Loading
Loading

Qeyd

Birinci test halında h = [3, 5, 5, 2, 6, 1] və uyğun bölgü mövcuddur, ona görə də cavab YES-dir.

  • Məsələn, azalmayan alt ardıcıllıq , artmayan alt ardıcıllıq isə 5, 5, 2, 1 ola bilər.

  • Başqa uyğun bölgü: azalmayan alt ardıcıllıq 3, 5, 5, 6, artmayan alt ardıcıllıq isə .

Şəkildə bu bölgülərdən birincisi göstərilib: azalmayan alt ardıcıllıq tünd (bütöv xətt), artmayan isə açıq (qırıq xətt) rəngdədir.

İkinci test halında h = [2, 1, 4, 3]. Tutaq ki, elementi artmayan alt ardıcıllığa aiddir.

  • Onda ondan əvvəl gələn və ondan kiçik olan və elementləri bu alt ardıcıllığa aid ola bilməz, deməli, hər ikisi azalmayan alt ardıcıllığa aiddir, lakin bu alt ardıcıllıqda -dən sonra gələ bilməz.

  • Deməli, elementi azalmayan alt ardıcıllığa aiddir, onda ondan sonra gələn və ondan kiçik olan elementi artmayan alt ardıcıllığa aiddir.

  • İndi və elementləri -dən əvvəl gəlir və ondan kiçikdir, ona görə də onlar artmayan alt ardıcıllığa aid ola bilməz və yenə hər ikisi azalmayan alt ardıcıllığa aid olmalıdır, bu isə mümkün deyil.

Buna görə cavab NO-dur.

Üçüncü test halında bütün elementlər bir alt ardıcıllığa aid ola bilər, digəri isə boş qalır.

Beşinci test halında artmayan alt ardıcıllıq , azalmayan alt ardıcıllıq isə -dür.