2. If we have any cycle with len>3 

1 2 ... n-1 n

let's check edge from 1 to n-1. If it exists 1 n-1 n is correct answer,

else we have cycle 1 2 .. n-1(because of edge from n-1 to 1), that is shorter. Do it while len>3

Start with a set containing all nodes. Recurse on that:

1) If the set contains <= 2 nodes, no cycle is found here.

2) Pick the first node (say, X). Now, separate the other nodes into two sets, depending on the direction of the edge from that node to the node we picked. That is, put all nodes A such that the edge is from A to X in a set, and put all other nodes in another set.

Let's name the set with an edge from that set to node X with outward set, and the other set as inward set.

3) Iterate over all members of inward set, say, I, Iterate over all members of outward set, say, O. If an edge is present from I to O (in that direction), return the triple (I, O, X).

4) Otherwise, recurse on each of the outward set and inward set, separately.

This works in O(N^2)

So for F(A), each time, u divide A into two part, the first one of A contains all the elements that mod 2 equals 1, and the second one mod 2 equals 1+1=2(It should be 0 but it can be easier if u understand it as "2"). Then for each part, u do it again. This time, the first part contains the elements mod 2*2 equals 1 and second part contains the elements mod 2*2 equals 1+2, likely, the third part should be mod 2*2 = 2 and forth part mod 2*2 = 2+2.

Knowing above, we can do something just similar to a binary search in O(log n)(maybe?) time. Assume a function query(l,r,nowmod,nowrest,startid,endid); it returns the available sum from b[l] to b[r]. The other four parameter represent a segment from array b, start from "startid", and end with "endid" and all of the elements in it obey that they mod "nowmod" = "mowrest". Then, if l == startid and r == endid, u just calculate a part of arithmetic progression contains all of the numbers from 1 to n and between u and v. For this step, u can use the formula of the sum of arithmetic progression in O(1), right? Else, u should calculate a position "mid", where the array divide into two parts. If l>=mid+1, all of the needed number is in the right of the progression, so u call query(l,r,nowmod*2,nowmod+nowrest,mid+1,endid). Similarly, if r<=mid, u call query(l,r,nowmod*2,nowmod,startid,mid). The other situation is l<=mid and r>=mid+1，u just break it into two parts, and return query(l,mid,nowmod*2,nowrest,startid,mid)