Merge Intervals

Problem statement

A studio receives room reservations as closed time intervals. Merge reservations that overlap or touch at an endpoint. Return the resulting disjoint intervals in increasing start-time order.

Input format

First line: n. Next n lines: start end.

Output format

Print the number of merged intervals, then one start end pair per line, sorted by start.

Constraints

1 <= n <= 100000; 0 <= start <= end <= 1000000000.

Sample input

4
5 8
1 3
3 6
10 12

Sample output

2
1 8
10 12