Игрушка детства

시간 제한2초메모리 제한1024 MB

요약

0 배열에서 시작해 m개의 구간 증가 연산을 적용한 결과가 a[i]를 넘지 않도록, 제거해야 할 연산의 최소 개수를 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 구간, 정렬, 누적 합
정답자: 아직 제출이 없습니다

문제

Однажды, убираясь в комнате, Паша нашел массив, с которым он очень любил играть в детстве. Однако, сейчас Паша понимает, что массивы, в которых на $i$ -ом месте стоит число большее, чем $a\_i$ , являются очень некрасивыми.

Кроме массива, он нашел листок, на котором были написаны операции, с помощью которых найденный массив был получен из массива, заполненного нулями. Операции имели вид: <<на отрезке от $l$ до $r$ всем элементам добавить $1$ >>. Теперь Паша хочет убрать некоторые операции так, чтобы массив стал красивым. Помогите ему сэкономить время --- найдите минимальное число операций, которые требуется убрать!

입력

В первой строке входного файла задано одно число $n$ ( $1 \le n\le 10^5$ ) --- размер массива. Во второй строке задано $n$ чисел $a\_i$ ( $1 \le a\_i \le 10^5$ ) --- число в $i$ -ой ячейке массива. В третьей строке задано число $m$ ( $1 \le m \le 10^5$ ) --- число операций. В следующих $m$ строках задано по два числа $l\_i, r\_i$ ( $1 \le l \le r \le n$ ) - описание операций.

출력

Выведите одно число --- ответ на задачу.

힌트

В первом примере необходимо убрать, например, четвертый отрезок.

예제2

예제 1
입력
```
4
3 4 4 2
4
3 4
4 4
1 1
3 4
```
예상 출력
```
1
```

예제 2

입력

6
2 3 6 4 1 4
11
2 5
1 5
2 2
3 3
1 1
3 3
3 5
4 4
2 2
1 6
3 5

예상 출력