Show this function on sequences is cyclical.
Very nice observation.
As you note, for the conjecture it suffices to prove $\phi^3=\phi$.
Call sequences $a=(a_1,a_2,\dots)$ and $b=(b_1,b_2,\dots)$ similar, if $\phi a=\phi b$, i.e. for each index $n$, $\ a_n$ occurs the same times among $a_1,\dots,a_n\ $ as $\ b_n$ among $b_1,\dots,b_n$.
For example, the sequences $(1,1,2,2,3,3,1),\ (1,1,2,2,3,3,2),\ (1,1,2,2,3,3,3)$ are similar.
We have to show that $\phi^2 a$ is similar to $a$ for an arbitrary sequence $a$.
Assume it holds for $n$ long sequences, and take $a_{n+1}$ in $a=(a_1,\dots,a_{n+1})$.
- It is either a 'new element' ($\phi a(n+1)=1$), in which case the number of $1$'s that denotes the new elements, is increased by one in $\phi a$, implying $\phi^2 a(n+1)=|\{a_1,\dots,a_{n+1}\}|$ which is a new element in the sequence $\phi^2a$.
- Or, it is a repeating element, and $s:=\phi a(n+1)=|\{i\le n+1:a_i=a_{n+1}\}|$.
This $s$ occurs in $\phi a$ for exactly $q$ times, where $q$ is the number of $a_i$'s occuring exactly $s$ times in $a$. (If $s$ is new, then $q=1$, and $a_{n+1}$ can be replaced by any of these $a_i$'s to get a similar sequence.)
On one hand, it means $\phi^2 a(n+1)=q$.
On the other hand, $q$ already occured in $\phi^2 a(1,\dots,n)$ exactly $s-1=|\{i\le n:a_i=a_{n+1}\}|$ times.
Another approach
Call a sequence $a$ of positive integers a regular sequence, if for all $n$,
- $\ 1\le a_n\le\max_{i<n}a_i+1$
- In every initial segment of $a$, the number of $x$'s is at least the number of $y$'s whenever $x\le y$.
Note that 2. can be rephrased as: if $a_n=a_i$ for some $i<n$, then $a_n$ is minimal among those sequence elements which occur exactly $(\phi a)_n-1$ times in $(a_1,\dots,a_{n-1})$
[because $a_n$ in $(a_1,\dots,a_n)$
has one more occurances than any of them].
For example, $(1,2,2)$ and $(1,2,3,2)$ are not regular, while $(1,2,1)$ and $(1,2,3,1)$ are regular.
Proposition.
$\ $ a) $\ \phi a$ is regular for any sequence $a$.
$\ $ b) $\ $If $a$ is a regular sequence, then $\phi^2 a=a$.