I thought for many days about how do i solve this problem: http://mirror.codeforces.com/contest/475/problem/D But it seems to me that I cannot get any better than O(N^2). I think there is a knowledge gap(mathematics). I looked through the editorial too. But I cannot understand. I want to understand the solution. I even looked many of the submissions(using sparse tables, segment trees...). But staring the code doesn't seem to be beneficial(or may be I am too dumb for the problem). So, please help me solve this problem. I just want the idea. Thank you coders!