Model the problem as a graph, drawing directed edges from $i \longrightarrow j$, such that $i / 3 = j$ ($i$ must be a multiple of $3$) or $2i = j$, for each ordered pair $i, j$ where $i \not = j$.
Note that the problem gives the bound $1 \leq a_i \leq 10^{18}$, for $i = 0, \dots, n-1$, so we need to use long long.
This gives room for integers up to $2^{63}-1$, which leaves us plenty of room (even if we're careless doing our checks; since, at
worst, $3 * 10^{18} < 2^{63}-1$)