Clan Expansion

The island of Teliarganj is divided into $N$ distinct territories ruled by several different clans, each having an unique integer between $1$ and $N$ assigned to it. The island can be considered a linear place, with the $i$-th territory located next to the $(i+1)$-th one. The $i$-th territory is initially ruled by clan $A_i$. Chef does not like this division of the island into several clans, an