Don't be so critical!

http://codeforces.com/blog/entry/51001#comment-349145

by the way, the typo was really funny :D

Minimize the number of cycles.

The answer to the fully given array = N — number of cycles. So you collect all cycle segments (e.g. ? -> 1 -> 4 -> 5 -> ?) where ? is controlled by you. If you have one segment — you have no choice (just put one element you have). Otherwise you can connect all segments into a one cycle (e.g. end0 -> start1, end1 ->start2, ... endI->start0), thus maximizing the answer.

Yes, it does. I solved it by MO.

I tried to, but got TLE :(

First, transform array into prefix sums + lift it up by 100000 to avoid negative values. So our goal is to find longest interval such that arr[l] = arr[r] inside the quered interval.

We start MO's algorithm and check intervals. We maintain:

• for each value: a deque of indices of this value in our current interval (easy to add/remove index from any side);
• a multiset of maximal lengths for each value (that is multiset of all deque[val].front() - deque[val].back()). The multiset is also easy to update since we can compute the length for the value from the deque. The answer for current query is then the largest value in the multiset.

At the end of block check, we can clear the multiset directly, and clean the deque's by collapsing the current interval.

PS: I used map<int,int> instead of multiset.

Sure. You will be able to get it later in the trainings section