I got AC with a bruteforce (Depth First Search) algorithm in 0.218 sec.

If you get TLE at test 39, it is something like this:
N = 100
The element of A is all 0, except for a(99, 100) = a(100, 99) = 1.