Степан веде журнал сну. Журнал представлено у вигляді послідовності непарної довжини \(A=(A_1 ​ (=0),A_2 ​ ,…,A_N ​)\), де непарні елементи позначають час, коли він встав, а парні — час, коли він пішов спати.

Більш формально, після запуску журналу сну він мав наступні сеанси сну.

• Для кожного цілого \(i\) такого, що \(1≤i≤(N−1)/2\) ​, він заснув рівно через \(A_{2i}\) ​ хвилин після початку журналу сну і прокинувся рівно через \(A_{2i+1}\) ​ хвилин після початку журналу сну.
• Він не заснув і не прокинувся в інший час.

Дайте відповіді на такі \(Q\) запитань. Для \(i\)-го запитання вам дано пару цілих чисел \((l_i ,r_i )\), для яких \(0≤l_i ≤r_i ≤A_N\) ​.

• Яка загальна кількість хвилин, протягом яких Степан спав протягом \(r_i ​ −l_i\) ​ хвилин від рівно від \(l_i\) ​ хвилини до \(r_i\) ​ хвилини після початку журналу сну?

Обмеження

• \(3≤N<2×10^5\)
• \(N\) є непарним.
• \(0=A_1 ​ <A_2 ​ <⋯<A_N ​ ≤10^9\)
• \(1≤Q≤2×10^5\)
• \(0≤l_i ​ ≤r_i ​ ≤A_N\) ​  \((1≤i≤Q)\)
• Усі вхідні значення є цілими числами.

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

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

Наступний   рядок містить цілі числа \(A_i\).

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

Наступні  \(Q\) рядків містять цілі числа \(l_i, r_i\).

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

У вихідний потік виведіть відповідь у \(Q\) рядках. В \(i\)-му рядку має бути ціле число, що відповідає \(i\)-му питанню.

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

7
0 240 720 1320 1440 1800 2160
3
480 1920
720 1200
0 2160

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

480
0
960

Степан спав, як показано на малюнку нижче.

Відповіді на кожне питання наступні.

• Між 480 хвилинами і 1920 хвилинами після запуску журналу сну Степан спав від 480 хвилин до 720 хвилин, від 1320 хвилин до 1440 хвилин і від 1800 хвилин до 1920 хвилин за 3 сеанси сну. Загальний час сну 240+120+120=480 хвилин.
• Між 720 і 1200 хвилинами після запуску журналу сну Степан не спав. Загальний час сну 0 хвилин.
• Від 0 хвилин до 2160 хвилин після запуску журналу сну Степан спав від 240 хвилин до 720 хвилин, від 1320 хвилин до 1440 хвилин і від 1800 хвилин до 2160 хвилин протягом 3 сеансів сну. Загальний час сну становить 480+120+360=960 хвилин.

Таким чином, три рядки вихідних даних повинні містити 480, 0 і 960.

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

21
0 20 62 192 284 310 323 324 352 374 409 452 486 512 523 594 677 814 838 946 1000
10
77 721
255 541
478 970
369 466
343 541
42 165
16 618
222 592
730 983
338 747

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

296
150
150
49
89
20
279
183
61
177