17353번 - 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

문제

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

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 ≤ 10⁵)

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

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

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

출력

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

제한

힌트