건초 더미 쌓기

최근 농장에서 저지른 온갖 장난이 미안했던 베시는, 농부 존에게 새로 들어온 건초 더미를 쌓는 일을 돕기로 했다.

처음에는 $1$번부터 $N$번까지 번호가 매겨진, 비어 있는 더미가 $N$개 있다 ($1 \le N \le 1000000$, $N$은 홀수). 존은 베시에게 $K$개의 지시를 차례로 내린다 ($1 \le K \le 25000$). 각 지시는 "$A$ $B$" 형태이며, 이는 $A$번부터 $B$번까지 범위에 있는 모든 더미의 맨 위에 새 건초 더미를 하나씩 올리라는 뜻이다. 예를 들어 지시가 "$10$ $13$"이라면, 베시는 $10$, $11$, $12$, $13$번 더미에 각각 건초를 하나씩 올린다.

베시가 모든 지시를 마친 뒤, 존은 $N$개의 더미의 중앙값 높이를 알고 싶어 한다. 즉, 더미들을 높이 순으로 정렬했을 때 한가운데에 오는 더미의 높이다. $N$이 홀수이므로 이 더미는 유일하게 정해진다. 베시가 답을 구할 수 있도록 도와주자.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $K$.
• 둘째 줄부터 $K$개의 줄: 각 줄에는 지시 하나가 공백으로 구분된 두 정수 $A$ $B$ ($1 \le A \le B \le N$) 형태로 주어진다.

• 모든 지시를 마친 뒤 더미 높이의 중앙값을 한 줄에 출력한다.

$N = 7$개의 더미가 있고 $K = 4$개의 지시가 주어지는 경우를 살펴보자. 지시를 모두 처리하면 각 더미의 높이는 차례로 $0, 1, 2, 3, 3, 1, 0$이 된다. 이를 정렬하면 $0, 0, 1, 1, 2, 3, 3$이고, 한가운데(네 번째) 값이 $1$이므로 중앙값은 $1$이다.