I think that most people trying to solve this problem will try to deal with two problems, they are:
1. How to calculate a[n] fast?
2. How to find those n that a[n] is the maximum in [1...n]?
Here is my method.

1. Calculating a[n] (without calculating a[1...n-1]).
Directly calculation will lead to a long time.
But, after some observation, I found that:
a[4n] = a[n]
a[4n + 1] = a[2n] + a[2n + 1] = 2a[n] + a[n + 1]
a[4n + 2] = a[n] + a[n + 1]
a[4n + 3] = a[n] + 2a[n + 1]
So, a[4n] to a[4n + 3] could be presented as the linear form of a[n] and a[n + 1].
We will soon realise that, a[2^k n] to a[2^k n + (2^k - 1)]  could also be presented as linear form of a[n] and a[n + 1].
So, pre-calculation is done to calculate all the linear forms of a[65536n] to a[65536n + 65535]. This will take about O(65536 * 2) time.
After this pre-calc, calculation for any number K will go very fast.

2. Finding the maximum.
After listing some of the 'maximum index', we found that:
1
3
5
9
11
19
21
35
37
43
......
Maybe my math is not so good, so I could not find so useful properties in the array, but I noticed one thing:
------------------------------------------------------------------------------------------
Every 'maximunm index' could be presented as its max 2-power and some former 'maximum index'.
------------------------------------------------------------------------------------------
Sorry for my poor English, let's take a look at the examples:
1
3 = 2 + 1
5 = 4 + 1
9 = 8 + 1
11 = 8 + 3
19 = 16 + 3
21 = 16 + 5
35 = 32 + 3
37 = 32 + 5
43 = 32 + 11
......
So, we just need to use every 2^k number to ITERATE the list of 'maximum index'. As the list is of size O(Log N), the algo runs quite fast.

With above methods, I got AC in 0.046 sec.

Well, if my algo is too stupid for you, don't hesitate to post your algo here.

Have fun and good luck.

thank you