I want to design an algorithm that given an array of size $n$, $A$ as an input, it outputs the number of times it has to do the following as the only way to copy $A$ into a new array $S$ of also size $n$:
Method of Copy Over $A$: given a range, $[a, b]$, where $1 \leq a \leq b \leq n$ and $i \in \{1, 2, ..., n \}$, the operation can set an integer, $x$ from $A$ continuously from $S[a]$ to $S[b]$.
An example is, let $A = <4, 37, 59, 4>$ and let $S = <0, 0, 0, 0>$ initially. In order to copy $A$ into $S$, we do
- $x = 4$ for $[a, b] = [1, 4]$: $S = <4, 4, 4, 4>$
- $x = 37$ for $[a, b] = [2, 2]$: $S = <4, 37, 4, 4>$
- $x = 59$ for $[a, b] = [3, 3]$: $S = <4, 37, 59, 4>$
So, the algorithm would return 3 since it took 3 operations to copy $A$ into $S$.
As an initial step I've considered creating a hash table where the keys are the distinct elements in $A$ and for each key, the value is a list of the indices in which that element occurs. Then finding all the disjointed subsets