数論階層クラスタリング C編（paizaランク S 相当）

長さ N の正整数列 A = (a_1, a_2, ..., a_N) が与えられます。ここで、N は奇数で、A は {1, 2, ..., N} の順列になっています。


長さが 3 以上の数列 A に対して、以下のような一連の操作を考えます。

・数列 A の任意の場所から連続する 3 つの要素を取り出し、これらを順に x, y, z とする。
・取り出した 3 つの要素があった位置に、gcd(x, y), gcd(y, z), gcd(z, x) のうちいずれか 1 つを挿入する。


数列 A の要素数は、1 回の操作につき 2 減少します。そこで、この操作を A の⻑さが 1 になるまで繰り返したときに、最終的に残る値としてありうる最大のものを求めてください。