14845번 - 컵과 구슬

홍준이와 명우는 놀기 좋아한다. 심심하던 홍준이는 다음과 같은 놀이를 생각해냈다.

1번부터 n번까지 서로 다른 번호를 가지는, 컵 n개와 구슬 n개가 있다. 홍준이는 각 컵마다 구슬을 하나씩 넣고, 컵의 번호 순서대로 일렬로 놓았다. 즉, 초기에 i번 컵에는 a_i번 구슬이 있다.
홍준이는 총 m번의 마법을 사용한다. 마법이 한 번 수행되면, l_i번 컵과 r_i번 컵 사이에 있는 모든 컵 안의 구슬들을 번호 오름차순 혹은 내림차순으로 정렬하여, 작은 번호의 컵부터 차례로 구슬을 1개씩 할당한다.

마법이 모두 끝나면, 홍준이는 명우에게 (n+1)/2번 컵에 몇 번 구슬이 있는지 묻는다. n은 홀수임이 보장된다.

예를 들어, n=5,m=2이고 a=[5,1,4,2,3]인 경우를 살펴보자. 첫 번째 마법이 1번 컵부터 4번 컵에 있는 구슬을 오름차순 정렬하는 것이라면, a=[1,2,4,5,3]로 바뀐다. 두 번째 마법이 2번 컵부터 5번 컵에 있는 구슬을 내림차순 정렬하는 것이라면, a=[1,5,4,3,2]로 바뀐다. 최종적으로 3번 컵에는 4번 구슬이 있게 된다.

여러분은 명우를 도와 홍준이의 질문에 대신 답을 해주는 프로그램을 작성하자.

첫째 줄에 두 정수 n과 m (1 ≤ n ≤ 99,999, 0 ≤ m ≤ 100,000)이 주어진다.

둘째 줄에 n개 정수 a₁,a₂,…,a_n (1 ≤ a_i ≤ n)이 주어진다. a는 1,2,…,n의 순열이다.

셋째 줄부터 m개의 줄에 걸쳐서 홍준이가 수행하는 마법이 순서대로 주어진다.

각 마법은 l_i와 r_i  (1 ≤ l_i, r_i ≤ n)로 구성되며, l_i < r_i이면 구슬을 번호 오름차순으로 정렬하고 l_i ≥ r_i이면 구슬을 번호 내림차순으로 정렬하는 것이다.

홍준이가 m번의 마법을 수행한 이후에 (n+1)/2번째 컵에 몇 번 구슬이 있는지 출력한다.