With help of my friend that was just looking at maximums index sequense and found an idea, finally, I got AC.
Some hints:
1) Find an idea to calculate next maximum indices from previous ones: all the maximum's indices can be obtained from previous ones in such ways:
i = s*2 + 1; or
i = s*2 - 1; or
i = s*4 + 1; or
i = s*4 - 1;

for example f(21)=8 is maximum for 21<=n<=34
so 21 = 2*11-1, where 11 is one of previous maximums indices. And so on using all the formulas above.
but 2*11+1 = 23 is not a maximum index. so we have to cancel  this number (23).
2) Learn to calculate f(n) in O(logn)
3) Generate all maximums indices (about 1500). You can store them in heap to get an access to the smallest maximum index.
4) than read n and just search for it in maximums index array.
P.S. who can prove the first and the main idea? If you can, please post here you proof.

How did you invent it?

Edited by author 05.07.2009 22:51

It seems that only test s*2 - 1 and s*4 - 1 is OK.
I've tested by bruteforce program in range [0, 20000000].
I will try it.

Edited by author 15.10.2016 08:24

This is exactly how my accepted program runs. Suppose i is a maximum index, i = 2*i1+1, i2 = i1+1, then either 1) i1 is even, at least one of i1/2, i2 is a maximum index; or 2) i2 is even, at least one of i2/2, i1 is a maximum index. But I don't know how to prove it. Thus candidate indices from 2^n to 2^{n+1} can be generated from calculated maximum indices from 2^{n-2} to 2^n.