410026: GYM103920 D Coats of Paint

For National Rock Day, you've decided to paint the rock that you were gifted. This is a peculiar rock that is divided into $$$n$$$ sections, numbered $$$1,...,n$$$. Every second for the next $$$x$$$ seconds, your friend will give you two numbers. The first number will represent the section that you should start painting at and then the second number will represent the section that you should stop painting at (both inclusive). Every coat of paint will have a thickness of 1. Can you find the section with the largest thickness at any point in the rock after all layers of paint have been applied?

The first line contains one number $$$n$$$ ($$$1 \leq n \leq 10^5$$$), representing the number of sections the rock is divided into. The second line contains one number $$$x$$$ ($$$1 \leq x \leq 100$$$), representing the number of times your friend will give you starting and stopping numbers.

The next $$$x$$$ lines will each contain two integers $$$i, j$$$ ($$$1 \leq i \leq j \leq n$$$) representing the starting and stopping sections to paint.

Output the region of the rock that has the greatest thickness (has the most coats of paint). If there are multiple, return the lowest section number.

5
1
2 4

2

10
3
3 5
4 8
5 9

5