Hi all,

I have been struggling with this problem for a long time, that would be really helpful if you could give me some hints :)

Given an array A of N elements integer number. N can be up to 200000. Each element A[i] ranges from -1e9 to 1e9, no element equals to Zero (0). We define a "valid" sequence such that 1. {x, -x} is valid sequence. 2. {x, S, -x} is valid sequence if S is a valid sequence. 3. {S1, S2} is valid sequence if S1, S2 are both valid sequences.

There are M queries, M can be up to 200000. Each query asks you to find the longest valid sequence in range [L, R] with 1 <= L <= R <= N.

Link to the problem: http://vn.spoj.com/VM14/problems/VMLSEQ/ (Vietnamese, my friend told me the contest is over so submission is not allowed anymore, but I think it's still very interesting/hard problem for discussion)

I came up with a hashing — based method to compute the "nearest" index j for each index i so that sequence [i, j] is valid, but I couldn't go any further. I thought the solution could be some kinds of merging — technique with two consecutive ranges in Interval tree (suffix — prefix), but so far I have no efficient method for that :(