Finally i proved why it works.

w2 function works like this: If there is a even number that can be rewritten as sum of two odd numbers/2 (one in left side and other in right side) , it returns false, otherwise true.

If we have w2() as a black box, we can solve this problem.

First check even numbers by odd numbers. (w2(v)).

Then check odd numbers by even numbers(--v , w2(v)).

It remains to check even numbers by even numbers and odd numbers by odd numbers. So we split the sequence in two sequence of even numbers and odd numbers , and for making new sequences (l and r) a permutation , we divide each number by two.(To easily use the same function Work)

How w2() works? It depends on a lemma :

--For an even number v[i] , if sum of the biggest odd number on the right (ohi) and on the left (hi) is bigger than 2*v[i] , and sum of the smallest odd number on the right(olo) and on the left(lo) is smaller than 2*v[i] , there is at least one arithmetic sequence of length 3.

--Proof : If v[i] = 2*k , and there is an j that 2*k-j lies on different side than 2*k+j , 2*k-j , 2*k and 2*k+j make the requested sequence. Other way for each j that 1 <= 2*k-j , 2*k+j <= n , 2*k-j , 2*k+j lie on the same side. We prove by induction on difference with 2*k that all elements in {2*k-1,2*k+1,2*k-3,2*k+3,...} lie on the same side.(That it is impossible , because there should be at least one element in the other side to get its minimum and maximum) The basis is obvious : 2*k-1 and 2*k+1 are on the same side.(otherwise there would be a arithmetic sequence)

Due to symmetry suppose that sequence likes this. ...2k...2k+1...2k-1... 2k+3 is in the right side of 2k , otherway we have(2k+3,2k+1,2k-1), and 2k-3 is in the same side with 2k+3.(right of 2k) By the same argument 2k+3 is in the right side of 2k+1 , and 2k-3 is in the left side of 2k-1.

With some similar argument we can show always 2k+o , 2k-o , 2k+o+2 , 2k+o-2 are in right side of 2k ,(o is a odd number) and if 2k+o+2 is in right side of 2k+o ,, 2k-o-2 is in left side of 2k-o , and vice versa.

For showing this for o+4 and o+2 , we first show that 2k+o+4 is in the right side. If 2k+o+4 is in left side , 2k+o+4 , 2k+o+2 , 2k+o make a good sequence or 2k-o-4 , 2k-o-2 , 2k-o make a good sequnce. For the remain suppose this positions :

a)...2k...2k+o...2k+o+2...2k-o-2...2k-o... --> 2k+o+4 is in left side of 2k+o+2 and 2k-o-4 is in right side of 2k-o-2

b)...2k...2k+o+2...2k+o...2k-o...2k-o-2... --> 2k+o+4 is in right side of 2k+o+2 and 2k-o-4 is in left side of 2k-o-2

c)...2k...2k+o+2...2k-o...2k+o...2k-o-2... --> 2k+o+4 is in right side of 2k+o+2 and 2k-o-4 is in left side of 2k-o-2

d)...2k...2k-o...2k+o+2...2k-o-2...2k+o... --> 2k+o+4 is in right side of 2k+o+2 and 2k-o-4 is in left side of 2k-o-2

Other positions can be proved by symmetry.

By knowing this lemma w2() is simple :).

I hope this proof to be correct and helpful. :)