This is a made up question not seen somewhere so I am not sure if a good solution exists but here it is anyways.

Given an array $$$ A $$$ of $$$ N $$$ non-negative integers, find the longest non-decreasing subsequence of this array such that every adjacent pair in the subsequence is co-prime, ie. $$$ gcd(a_{i}, a_{i + 1}) = 1 \space \forall \space 0 <= i < K - 1 $$$ where $$$ K $$$ is length of subsequence.

Would it be possible to have a solution better than $$$ O(N^2) $$$ if the numbers in this array will be upto $$$ 10^5 $$$ ?

I was exploring solutions using segment trees but it's very tricky, compared to a different version where adjacent pairs should be strictly non-coprime which would be trivial.

If there is some way to make it more efficient I would like to know.