Nice problem $\color{black}\rule{25cm}{1pt}$ The maximum is $N_{max}=\left\lfloor\frac{n^2}{4}\right\rfloor$ Let's say we are given the maximal sequence $a_1,a_2,\dots ,a_n$. We easily notice that if a prime of an exponent fully divisible by $3$ fully divides (that means $v_p(a_i)=3k$) some element of the sequence we can "remove" it and create a new maximal sequence $b_1,b_2,\dots ,b_n$. Now from this sequence we have that the prime factorization of every single element of $b_1,b_2,\dots ,b_n$ is either $\equiv 1\mod 3$ or $\equiv 2 \mod 3$. But notice that degree of freedom we have here, let's say that a prime $q$ divides some element of the sequence, then for surely $q$ must also divide some other element of the sequence. This implies that we can get rid of every singles prime except one, thus we form a new sequence $c_1,c_2, \dots ,c_n$. We do this since we can easily backtrack and multiply $c_i$ by the right amount to get $b_i$. Thus we have reduced the argument down to the prime powers, where the powers are $\equiv 1\mod 3$ or $\equiv 2 \mod 3$. Now we claim that the following construction will give us the maximum. $\color{red}\rule{25cm}{0.5pt}$ The construction: Place all the prime powers whose exponents are $\equiv 1 \mod 3$ on one side, such that there is exactly $\left \lfloor \frac{n}{2} \right \rfloor$ members of that sort, the other elements are prime powers whose exponents are $\equiv 2 \mod 3$ and they are on the other side. $\color{red}\rule{25cm}{0.5pt}$ To show this we use inequalities. Place all the members of the sequence on a line. We shall assume that the first element has a power $\equiv 1 \mod 3$, we assume this w.l.o.g. After they have been placed on the line call a segment the longest subsequence such that all the exponents are all of the same residue mod $3$, the length of a segment is the number of members on the segment. We color in the segments with either red or blue, where red represents the one with exponents $1$ mod $3$ and blue the other ones. We name these red segments from left to right $1,2,\dots ,\text{etc}$, and we call the blue segments $1,2,\dots ,\text{etc}$ as well. Let $x_i$ the length of all the red segments and $y_i$ the length of all the blue segments, where $x_i$ represents the length of the $i^{th}$ red segment and $y_i$ represents the length of the $i^{th}$ blue segment, thus we have that: $$N=\sum_{t=1} x_t.\sum_{k \geq t} y_k$$but we have that: $$N \leq \left(\sum x_i\right)\left(\sum y_i\right)$$ But notice that the $RHS$ of the inequality is less than: $$\left(\sum x_i\right)\left(\sum y_i\right)\leq \left\lfloor \frac{n^2}{4}\right\rfloor$$the only time when this is the upper bound is when we have our construction. Thus we have that $N_{max} = \left \lfloor \frac{n^2}{4} \right \rfloor$