| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 13 | 10 | 7 | 70.000% |
Однажды, убираясь в комнате, Паша нашел массив, с которым он очень любил играть в детстве. Однако, сейчас Паша понимает, что массивы, в которых на $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$) - описание операций.
Выведите одно число --- ответ на задачу.
4 3 4 4 2 4 3 4 4 4 1 1 3 4
1
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
4
В первом примере необходимо убрать, например, четвертый отрезок.