After reading the editorial and going through some blogs, I made an implementation of the Union-Find Data Structure in Python and tried to solve the problem using it. But I am getting a TLE. Here is the link to my last solution. In the data structure, I used both path compression and union by rank. Please help.

There was one small bug in your solution, you missed out N in your list of midpoints. But anyway the time limit is simply too strict for Python I think
It is quite easily accepted using PyPy, but I just couldn’t get it to pass using Python 3.5. I tried to optimize it by getting rid of anything unnecessary and all function calls, but it still times out. Here is my last version if it helps you.