길이가 N인 수열이 주어지고, 이후 Q개의 쿼리가 주어진다. 각 쿼리는 각 줄에 다음과 같은 두 개의 수로 주어진다.
l r: A_l + A_l+1 + … + A_r-1 + A_r의 값을 출력한다. (1 ≤ l ≤ r ≤ N)

주어지는 쿼리를 처리하는 프로그램을 작성하시오.

첫째 줄에 수열의 길이 N이 주어진다. (1 ≤ N ≤ 10⁵)
둘째 줄에 A₁, A₂, … , A_n-1, A_n이 주어진다. (1 ≤ A_i ≤ 10⁹)
셋째 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 10⁵)
넷째 줄부터 M개의 줄에 쿼리가 주어진다.

각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.

1 3의 경우 1번째부터 3번째까지의 원소를 더하라는 의미이므로 1+2+3=6을 출력하였다.
이후의 쿼리도 동일하게 적용된다.

컴퓨터에게 100억 번의 계산은 1초로는 턱없이 부족하다.
시간 초과를 받았다면 다른 방법을 생각해 보라.