Gecə Növbətçiləri üçün imtahan

Andallar və İlk İnsanlar dövründən bəri Westerosda $f(p)$ funksiyası məlumdur, burada $p$ istənilən uzunluqda bir permutasiyadır. O, aşağıdakı kimi təyin olunur.

$d$ massivini belə təyin edək: 1 \le i \le m-1 üçün d_i = |p_i - p_{i+1}|, burada $m$ permutasiyanın uzunluğudur. Sonra $f(p)$, 1 \le i \le m-2 olan və d_i \not\equiv d_{i+1} \pmod{2} şərtini ödəyən indekslərin sayına bərabərdir.

Jon Snow uşaqlıqdan bəri Gecə Növbətçilərinə qoşulmağı arzulayır, buna görə də imtahan verəcək. İmtahanın mahiyyəti $f(p)$ funksiyasının mümkün olan ən böyük qiymətinə malik uzunluğu $n$ olan bir permutasiya tapmaqdır. Lakin imtahan götürən Ser Alliser Thorne Jon Snow-a nifrət edir və buna görə də ondan $f(p)$-nin maksimum qiymətinə çatan bütün permutasiyalar arasında leksikoqrafik cəhətdən ən kiçiyini tələb edir.

Jon Snow heç nə bilmədiyi üçün sizin köməyinizə ehtiyacı var. Zəhmət olmasa, ona Gecə Növbətçiləri üçün imtahandan keçməyə kömək edin.