시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 36 8 7 33.333%

문제

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

1번부터 n번까지 서로 다른 번호를 가지는, 컵 n개와 구슬 n개가 있다. 홍준이는 각 컵마다 구슬을 하나씩 넣고, 컵의 번호 순서대로 일렬로 놓았다. 즉, 초기에 i번 컵에는 ai번 구슬이 있다.
홍준이는 총 m번의 마법을 사용한다. 마법이 한 번 수행되면, li번 컵과 ri번 컵 사이에 있는 모든 컵 안의 구슬들을 번호 오름차순 혹은 내림차순으로 정렬하여, 작은 번호의 컵부터 차례로 구슬을 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개 정수 a1,a2,…,an (1 ≤ ai ≤ n)이 주어진다. a는 1,2,…,n의 순열이다.

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

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

출력

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

예제 입력 1

5 2
5 1 4 2 3
1 4
5 2

예제 출력 1

4

출처

  • 문제를 번역한 사람: appa