Summer in Tyago

I have thought lot about this problem but can’t think of solution less than O(N^2) please give some good editorial

//