Задача №112586. Игрушка детства
Однажды, убираясь в комнате, Паша нашел массив, с которым он очень любил играть в детстве. Однако, сейчас Паша понимает, что массивы, в которых на i -ом месте стоит число большее, чем a i , являются очень некрасивыми.
Кроме массива, он нашел листок, на котором были написаны операции, с помощью которых найденный массив был получен из массива, заполненного нулями. Операции имели вид: « на отрезке от l до r всем элементам добавить 1 ». Теперь Паша хочет убрать некоторые операции так, чтобы массив стал красивым. Помогите ему сэкономить время — найдите минимальное число операций, которые требуется убрать!
В первой строке входного файла задано одно число n ( 1 ≤ n ≤ 10 5 ) — размер массива. Во второй строке задано n чисел a i ( 1 ≤ a i ≤ 10 5 ) — число в i -ой ячейке массива. В третьей строке задано число m ( 1 ≤ m ≤ 10 5 ) — число операций. В следующих m строках задано по два числа l i , r i ( 1 ≤ l ≤ r ≤ n ) - описание операций.
Выведите одно число — ответ на задачу.
В первом примере необходимо убрать, например, четвертый отрезок.
Тесты к этой задаче состоят из трех групп:
-
Первая группа тестов состоит из тестов, для которых выполняется ограничение
n
≤ 15
,
m
≤ 15
. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет
20
баллов.
-
Вторая группа тестов состоит из тестов, для которых выполняется ограничение
n
≤ 1000
,
m
≤ 1000
. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет
40
баллов.
- Третья группа тестов состоит из тестов, для которых выполняется ограничение n , m ≤ 10 5 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.
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