Ardıcıllığın əksinə çevrilməsi#10555

Ardıcıllığın əksinə çevrilməsi

1 saniyə

128 meqabayt

Çox çətin

Fermer Con öz $n$ inəyini şəkil çəkmək üçün bir sıra ilə düzür. Bu sırada $i$ -ci inəyin boyu $a_{i}$ a_i-dir və Fermer Con hesab edir ki, əgər sırada inəklərin boyuna görə uzun artan alt-ardıcıllığı olsa, şəkil daha estetik görünərdi.

Xatırladaq ki, alt-ardıcıllıq — ilkin ardıcıllığın elementlərindən ibarət $a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{k}}$ a_{i_1}, a_{i_2}, \ldots, a_{i_k} ardıcıllığıdır, uyğun indeksləri $i_{1} < i_{2} < \dots < i_{k}$ i_1 < i_2 < \ldots < i_k şərtini ödəyir. Alt-ardıcıllığı artan adlandırırıq, əgər $a_{i_{1}} \leq a_{i_{2}} \leq \dots \leq a_{i_{k}}$ a_{i_1} \le a_{i_2} \le \ldots \le a_{i_k} olarsa.

Fermer Con öz sırasında uzun artan alt-ardıcıllığın olmasını istəyir. Buna nail olmaq üçün o, inəklərin istənilən alt-ardıcıllığını seçib onun elementlərinin sırasını əksinə çevirə bilər.

Məsələn, inəklər aşağıdakı kimi düzülüb:

1 6 2 3 4 3 5 3 4

Aşağıda göstərilən elementləri seçə bilərik:

1 6 2 3 4 3 5 3 4
^ ^ ^ ^

və onların sırasını əksinə çevirərək aşağıdakını əldə edə bilərik:

1 4 2 3 4 3 3 5 6
^ ^ ^ ^

Diqqət edin ki, əksinə çevrilmiş elementlər əməliyyatdan əvvəlki ilə tam olaraq eyni mövqelər toplusunu tutur, digər bütün elementlər isə dəyişmədən qalır.

En çoxu bir alt-ardıcıllığın elementləri əksinə çevrildikdən sonra artan alt-ardıcıllığın mümkün olan maksimum uzunluğunu təyin edin.

Giriş

Birinci sətirdə $n (1 \leq n \leq 50)$ n~(1 \le n \le 50) ədədi verilir. Növbəti $n$ sətirdə $a_{1}, \dots, a_{n}$ a_1, \ldots, a_n verilir, burada hər bir $a_{i}$ a_i $1 \dots 50$ diapazonunda tam ədəddir.

Çıxış

En çoxu bir alt-ardıcıllığın elementlərinin sırası əksinə çevrildikdən sonra artan alt-ardıcıllığın mümkün olan maksimum uzunluğunu çap edin.

Nümunələr

Nümunə 1