Bir hərfli palindrom
Son zamanlarda "GoldSilver Software" adlı kompüter oyunları inkişaf etdirən şirkət "Bir hərfli palindrom" adlı yeni bir smartfon oyunu təqdim etdi. Oyun çox sadə olduğu üçün tez bir zamanda məşhurlaşdı.
Oyun, oyunçuya ana dilində N simvoldan ibarət S adlı bir sıra verilməsi ilə başlayır. Daha sonra istifadəçi müəyyən sayda hərəkətlərlə bu sıradan bir hərfli palindrom olan bir sıra əldə etməlidir. Bir hərəkətdə oyunçu sırada yan-yana duran iki simvolun yerini dəyişə bilər.
Şəkil №1. Bir hərfli palindrom nümunələri.
Sıra S bir hərfli palindrom adlanır, əgər elə bir təbii ədəd i varsa ki, 1 ≤ i ≤ N, S_i= S’_i, burada S^{’}_1^{ }= S_N_{, }S^{’}_2^{ }= S_N_{-1}, …. S^{’}_N^{ }= S_1_{. } Sıra S^{’} "əks" sıra S adlanır.
Şəkil №1. İkinci nümunənin təsviri, iki hərəkət ardıcıllığı.
Verilmiş sıra S üçün bir hərfli palindrom əldə etmək üçün lazım olan minimal hərəkət sayını müəyyən etmək lazımdır.
Giriş verilənləri
Giriş faylının ilk sətri bir tam ədəd N (2 ≤ N ≤ 250000) ehtiva edir.
Giriş faylının ikinci sətri sıra S-ni təsvir edir və N ədədini ehtiva edir, bu ədədlər 1 ilə 65535 arasında olan tam ədədlərdir və tək boşluqlarla ayrılır. Hər bir ədəd sıradakı müvafiq simvolun kodunu təmsil edir. Simvollar bərabər sayılır, əgər müvafiq kodları bərabərdirsə.
Çıxış verilənləri
Çıxış faylı bir ədəd ehtiva etməlidir – verilmiş sıra S-dən bir hərfli palindrom əldə etmək üçün lazım olan minimal hərəkət sayı. Həllin mövcudluğu təmin edilir.