시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 285 104 79 47.305%

문제

욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다.

  1. 별이 떨어지는 위치는 N개의 점이다. 점은 순서대로 1, 2, ..., N의 번호를 갖는다.
  2. 매일 밤 별들은 1, 2, ..., N의 연속한 부분 구간 [L, R]에 떨어진다.
  3. [L, R]에 별이 떨어지면, 각 점에는 순서대로 1, 2, ..., R-L+1개의 별이 떨어진다. 다시 말해, L에는 1개, L+1에는 2개, ..., R에는 R-L+1개의 별이 떨어진다.

욱제는 하늘에서 떨어지는 별들을 기록하다가 잠이 들어버렸다!! 혹시나 했지만 역시나, 여러분은 욱제를 대신해 아래의 쿼리를 수행해야 한다. (ㅎㅎ;; ㅈㅅ.. ㅋㅋ!!)

  • 1 L R: [L, R]에 별이 떨어진다. (1 ≤ L ≤ R ≤ N)
  • 2 X: 점 X에 떨어진 별의 개수의 합을 출력한다. (1 ≤ X ≤ N)

입력

첫째 줄에 별이 떨어지는 점의 개수 N이 주어진다. (1 ≤ N ≤ 105)

둘째 줄에 욱제가 잠들기 전까지 세어 놓은, 이미 떨어진 별들의 개수 A1, ..., AN이 공백을 사이에 두고 주어진다. (0 ≤ A1, ..., AN ≤ 106)

셋째 줄에는 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 105)

넷째 줄부터 Q개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

출력

2번 쿼리에 대한 답을 한 줄에 하나씩 출력한다.

예제 입력 1

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

예제 출력 1

6
10