\(N\) корів фермера Джона (\(1\le N\le 1,5\cdot 10^5\)) мають цілу продуктивність \(a_1,\dots,a_N\). Тобто \(i\)-а корова виробляє \(a_i\) одиниць молока за хвилину (\( 0 \leq a_i \leq 10^8 \)).

Щоранку фермер Джон починає з того, що всі \(N\) корів підключені до його доїння. Від нього потрібно відчеплювати їх по одній, відправляючи геть для їхніх щоденних вправ. Перша корова, яку він відправляє, знімається з гачка після всього 1 хвилини доїння, друга корова, яку він відправляє, відчеплюється після двох хвилин доїння і таке інше. Оскільки перша корова (скажімо, корова \(x\)) витрачає лише одну хвилину на доїльному апараті вона вносить лише \(a_x\) одиниць загальної кількості молока. Друга корова (скажімо, корова \(y\)) витрачає на доїння лише дві хвилини і таким чином дає \(2a_y\) одиниць загальної кількості молока. Третя корова (Скажімо, корова \(z\)) приносить всього \(3a_z\) одиниць і так далі. Нехай \(T\) є максимально можлива кількість молока, яку може зібрати фермер Джон, якщо він відчіплює своїх корів у оптимальному порядку.

Фермеру Джону цікаво, як вплине на \(T\), якщо частина продуктивності молока у його стаді були інші. Для кожного із запитів \(Q\) (\(1\le Q\le 1.5\cdot 10^5\)) кожне з яких задано двома цілими числами \(i\) і \(j\), будь ласка, розрахуйте, якою буде нове значення \(T\), якщо \(a_i\) було встановлено \(j\) (\(0 \leq j \leq 10^8\)). Зверніть увагу, що кожен запит розглядає тимчасову потенційну зміну незалежно від усіх інших запитів; тобто \(a_i\) повертається до вихідного значення перед наступним запитом.

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

Перший рядок містить \(N\).

Другий рядок містить \(a_1\dots a_N\).

Третій рядок містить \(Q\).

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

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

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

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

5
1 10 4 2 6
3
2 1
2 8
4 5

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

55
81
98

Для першого запиту \(a\) стане \([1,1,4,2,6]\), а \(Т = 1 \cdot 1 + 2 \cdot 1 + 3 \cdot 2 + 4 \cdot 4 + 5 \cdot 6 = 55 \).

Для другого запиту \(a\) стане \([1,8,4,2,6]\), а \(Т = 1 \cdot 1 + 2 \cdot 2 + 3 \cdot 4 + 4 \cdot 6 + 5 \cdot 8 = 81 \).

Для третього запиту \(a\) стане \([1,10,4,5,6]\), а \(Т = 1 \cdot 1 + 2 \cdot 4 + 3 \cdot 5 + 4 \cdot 6 + 5 \cdot 10 = 98 \).

ОЦІНКА:

• Тести 2–4: \(N,Q\le 1000\)
• Тести 5–11: без додаткових обмежень.