Nasser və bərabər massiv#13082

Nasser və bərabər massiv

1 saniyə

256 meqabayt

Nasserin $n$ müsbət tam ədəddən ibarət $a$ massivi var. O, aşağıdakı əməliyyatları istənilən sayda (o cümlədən sıfır dəfə) və istənilən ardıcıllıqla yerinə yetirə bilər:

1. $i$ indeksini ( $1 \leq i \leq n$ 1 \le i \le n) seçib $a_{i}$ a_i qiymətini $2$ vahid artırmaq.

2. $a_{l} = a_{l + 1} = \dots = a_{r}$ a_l = a_{l+1} = \ldots = a_r olacaq şəkildə $[l, r]$ [l, r] parçasını ( $1 \leq l < r \leq n$ 1 \le l < r \le n) seçib $a_{l}, a_{l + 1}, \dots, a_{r}$ a_l, a_{l+1}, \ldots, a_r ədədlərinin hər birini $1$ vahid artırmaq.

Nəzərə alın ki, ikinci əməliyyat üçün seçilmiş parça ən azı iki elementdən ibarət olmalı və əməliyyat anında bu elementlərin hamısı bərabər olmalıdır. Məsələn, əgər $a = [4, 5, 5, 7]$ a = [4, 5, 5, 7] olarsa, $[2, 3]$ parçasını seçmək olar, lakin $[1, 2]$ və $[2, 4]$ parçalarını seçmək olmaz.

Nasserin massivin bütün elementlərini bərabər edib-edə bilməyəcəyini müəyyən edin.

Giriş

Hər test bir neçə test nümunəsindən ibarətdir. Birinci sətirdə bir tam ədəd $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — test nümunələrinin sayı verilir. Sonra test nümunələrinin təsviri gəlir.

Hər test nümunəsinin birinci sətrində bir tam ədəd $n$ $(1 \leq n \leq 2 \cdot 1 0^{5})$ (1 \le n \le 2 \cdot 10^5) — massivin ölçüsü verilir.

Hər test nümunəsinin ikinci sətrində $n$ tam ədəd $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n $(1 \leq a_{i} \leq 1 0^{9})$ (1 \le a_i \le 10^9) — massivin elementləri verilir.

Bütün test nümunələri üzrə $n$ qiymətlərinin cəminin $2 \cdot 1 0^{5}$ 2 \cdot 10^5-i aşmadığı təmin edilir.

Çıxış

İcazə verilən əməliyyatlardan istifadə edərək bütün elementləri bərabər etmək mümkündürsə, YES çap edin. Əks halda NO çap edin.

Cavabı istənilən registrdə (böyük və ya kiçik hərflərlə) çıxara bilərsiniz. Məsələn, yEs, yes, Yes və YES sətirlərinin hamısı düzgün müsbət cavab kimi qəbul ediləcək.

Nümunələr

Nümunə 1

Qeyd

Birinci test nümunəsində $a = [1, 2]$ a = [1, 2]. $a_{2} - a_{1}$ a_2 - a_1 fərqi $1$ -ə bərabərdir. Birinci əməliyyat bu fərqi dəqiq $2$ vahid dəyişir, ona görə də fərq həmişə tək qalır və heç vaxt $0$ olmur. İkinci əməliyyatı yalnız iki bərabər qonşu elementə tətbiq etmək mümkündür, burada isə bu heç vaxt mümkün deyil. Deməli, elementlər heç vaxt bərabər ola bilməz.

İkinci test nümunəsində $a = [2, 4]$ a = [2, 4]. $i = 1$ i = 1 ilə birinci əməliyyatı tətbiq edirik: $[2, 4] \to [4, 4]$ [2, 4] \to [4, 4].

Dördüncü test nümunəsində $a = [3, 2, 2, 1]$ a = [3, 2, 2, 1]. $[l, r] = [2, 3]$ [l, r] = [2, 3] ilə ikinci əməliyyatı tətbiq edirik: $[3, 2, 2, 1] \to [3, 3, 3, 1]$ [3, 2, 2, 1] \to [3, 3, 3, 1]. Sonra $i = 4$ i = 4 ilə birinci əməliyyatı tətbiq edirik: $[3, 3, 3, 1] \to [3, 3, 3, 3]$ [3, 3, 3, 1] \to [3, 3, 3, 3].

Bal hesablama

Altməsələ $1$ ( $100$ bal) : Əlavə məhdudiyyət yoxdur.