IN: 3 0
OUT: 0

This test helped me :D
Good luck!

10
3
1 5
10 6
8 6

16
4
16 13
2 11
9 2
7 3

17
6
4 7
3 9
2 9
1 11
17 12
17 14

10
3
3 5
7 2
8 1

Try

8
4
2 4
4 6
6 8
8 2

Ans: 2 6 or 4 8

How many structures  need quick solution.
I worked with segments [i,j] on [1,N] and used
1: short num[50000] for quicksort of segments;
2: short prev[50000] for fathes of segments. Segment I is father of segment J if I smallest segment containing J.
3: vector<short>sons[50000] for sons of segments.
Last structure very slow and I had bad Ac time 0.95.

Is first test sample or not? Correct solution gets WA #1 :(((