**Обратите внимание: время на тест для этой задачи 5s, в 2.5 раза больше, чем обычно.
Предельный размер памяти также увеличен в два раза по сравнению с умолчанием.
Имеется \(N\) (\(1 \leq N \leq 2000\)) гор в ряд на ферме Джона
Это может быть выражено как массив высот \(h_1,h_2,\dots,h_N\).
Для горы \(i\), Вы можете увидеть другую гору \(j\) если нет гор строго выше чем линия взгляда,
соединяющая горы \(j\) и \(i\). Формально, для двух гор \(i < j\), они могут видеть
друг друга, если не существует такого \(k\) \(i < k < j\) и \((k, h_k)\) выше чем
отрезок, соединяющий \((i, h_i)\) и \((j, h_j)\). Имеется \(Q\) (\(1 \leq Q \leq 2000\))
изменений высот, когда высота одной горы возрастает. Определите общее количество
неупорядоченных пар гор, которые могут видеть друг друга после каждого изменения.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Строка
\(1\) содержит
\(N\).
Строка \(2\) содержит \(N\) высот \(h_1,h_2,\dots,h_N\) (для каждого \(i\),
\(0 \leq h_i \leq 10^9\)).
Строка \(3\) содержит \(Q\).
Строки \(4\) - \(3+Q\) содержат \(x\), \(y\) (\(1 \leq x \leq N\), \(1 \leq y\)) где \(x\) индекс
горы, \(y\) - величина на которую эта гора возрастает. Гарантируется, что новая высота горы не превысит
\(10^9\).
ФОРМАТ ВЫВОДА (на экран / stdout):
\(Q\) строк, на каждой общее количество неупорядоченных пар гор, которые могут
видеть друг друга после каждого обновления.
ПРМЕР ВВОДА:
5
2 4 3 1 5
3
4 3
1 3
3 2
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 4 3 1 5
3
4 3
1 3
3 2
|
7
10
7
|