Let us freeze the middle of an interesting sequence in all possible ways. It can easily be noticed that if there exists a sequence of length ~2N~, there also exists a sequence of length ~2M < 2N~ with the same middle value for each integer ~M~ less than ~N~. This suggests a binary search approach to be used to find the longest interesting sequence for every position of the middle element, which yields an algorithm with ~\mathcal O(N \log N)~ time complexity.

For each element, we first search for the longest sequence which starts with that element. To solve that problem, we process elements from right to left. Among all interesting sequences ~[a_i, b_i]~ which start before the position of the current element we are processing we search for the one for which the value ~(b_i-a_i+1)-2(X-a_i) = b_i+a_i+1-2X~ is maximal. The value of ~a_i~ can be found as follows: as we process the elements, we keep track of the maximum and we try to improve that maximum by considering interesting sequences which start at the current position.

When we move to the right, we decrease that maximum by ~2~ (since a move ~X := X+1~ decreases this value by ~2~).

The above algorithm can easily be implemented with ~\mathcal O(N \log N)~ time complexity, which solves the problem.