Problem
Anda diberi sehelai kertas berkotak-kotak yang diperbuat daripada n petak berwarna bernombor dari 1 hingga n dari kiri ke kanan. Petak ke-i pada mulanya berwarna c
i.
Kami mengatakan bahawa kuasa dua i dan j terletak dalam komponen yang sama jika c
i = c
j dan c
i = c
k untuk semua k memuaskan i < k < j. Dalam erti kata lain, semua petak pada segmen dari i hingga j mesti mempunyai warna yang sama.
Sebagai contoh, jalur [3,3,3] mempunyai 1 komponen yang disambungkan, manakala [5,2,4,4] mempunyai 3.
Isi permainan dimainkan pada jalur ini seperti berikut:
Pada permulaan permainan, anda memilih satu petak permulaan rawak (ini tidak dikira sebagai giliran).
Kemudian, pada setiap pergerakan, anda menukar warna komponen yang disambungkan yang mengandungi petak permulaan kepada mana-mana warna lain.
Ketahui bilangan minimum pergerakan yang diperlukan untuk mewarna semula keseluruhan jalur dalam satu warna.
Input:
Baris pertama mengandungi integer tunggal n (1 ≤ n ≤ 5000) — bilangan segi empat sama.
Baris kedua mengandungi integer c
1,c
2,…,c
n (1 ≤ c
i <5000) — warna awal segi empat sama.
Output:
Cetak satu integer — bilangan minimum pergerakan untuk dibuat.
Contoh:
| Input |
Output |
4
5 2 2 1
| 2 |
8
4 5 2 2 1 3 5 5
| 4 |
1
4 |
0 |
Penjelasan:
Salah satu cara optimum dalam contoh pertama: [5, 2, 2, 1] -> [5, 2, 2, 2] -> [5, 5, 5, 5]