Є \(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\)) змін висот, коли висота однієї гори зростає. Визначте загальну кількість невпорядкованих пар гір, які можуть бачити один одного після кожної зміни.

Формат вхідних даних

Рядок \(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\).

Формат вихідних даних

\(Q\) рядків, у кожному загальна кількість невпорядкованих пар гір, які можуть бачити один одного після кожного оновлення.

Приклад вхідних даних

5
2 4 3 1 5
3
4 3
1 3
3 2

Приклад вихідних даних

7
10
7

Спочатку наступні пари гір можуть бачити один одного: \((1, 2)\), \((2, 3)\), \((2, 5)\), \((3, 4)\), \((3, 5)\), \((4, 5)\), всього їх \(6\).

Після першого оновлення гора \(4\) отримає висоту \(4\). Це не блокує ніякої видимості, але робить так що тепер \(4\) може бачити \(2\), що збільшує відповідь до \(7\).

Після другого оновлення гора \(1\) стає висотою \(5\), що не блокує ніякої видимості, але робить так, що тепер \(1\) може бачити \(3\), \(4\), \(5\), що збільшує відповідь до \(10\).

Після третього оновлення гора \(3\) отримує висоту \(5\), і це блокує гору \(1\) від видимості \(4\), блокує гору \(2\) від видимості гір \(4\) і \(5\) таким чином виходить відповідь \(7\).

ОЦІНЮВАННЯ

• У тестах 2-5 \(N, Q\le 100\).
• У тестах 6-11 \( Q \leq 10 \).
• У тестах 12-21 немає додаткових обмежень.