Desperate Fire Survive

Rikka는 콘테스트가 열리는 홀까지 자신의 모든 셀과 함께 달리고 있다.

EC Final은 점점 커지고 있다. 약한 2000W 메인 선에 연결되는 컴퓨터가 계속 늘어나서, 모든 행에 열이 쌓이고 있다.

Rikka가 홀에 들어서자 LCR이 자원봉사자들과 함께 선을 다시 배치하고 있었다. 하지만 그녀는 지켜보는 것 말고는 도울 수 없을지도 모른다.

"들어 봐. 새 회로의 매개변수를 계산할 시간이 없어. 자료구조 잘 알아? 제발 도와줘..."

회로는 $n$개의 노드로 이루어진 수열이고, 노드의 레벨은 $1$부터 $m$까지 총 $m$종류가 있다. $k$레벨 노드의 전력 한도는 $(k-1)$레벨 노드의 두 배이므로, $k < m$이면 Rikka는 인접한 $k$레벨 노드 두 개를 $(k+1)$레벨 노드 하나로 합칠 수 있다. 또한 회로에서 노드를 언제든지 제거할 수 있으며, 남은 노드들의 순서는 그대로 유지된다.

자원봉사자들은 총 $q$개의 질의를 가지고 있다. 각 질의는 구간 $[l,r]$과 정수 레벨 $k$로 주어진다. Rikka는 주어진 구간의 부분 구간 중에서 $k$레벨 노드를 만들 수 있는 것의 개수를 세야 한다. 여기서 부분 구간은 $l \le x \le y \le r$을 만족하는 구간 $[x, y]$를 말한다. 구간 $[x, y]$가 $k$레벨 노드를 만들 수 있다는 것은, 같은 레벨의 인접 노드를 합치는 연산과 노드를 제거하는 연산을 반복해서 수열 $[x, y]$를 하나의 $k$레벨 노드로 바꿀 수 있다는 뜻이다. 두 연산은 임의의 순서로 몇 번이든 수행할 수 있다. 결과 레벨은 정확히 $k$여야 하며, 더 높거나 낮아서는 안 된다.

첫 줄에 세 정수 $n$, $m$, $q$ ($1 \le n, m, q \le 2 \times 10^5$)가 주어진다. 각각 회로 수열의 길이, 최대 레벨, 질의의 개수이다.

둘째 줄에는 노드의 레벨을 순서대로 나타내는 정수 $A_1, A_2, \dots, A_n$ ($1 \le A_i \le m$)이 주어진다.

이어지는 $q$개의 줄에는 각각 질의를 나타내는 세 정수 $l$, $r$, $k$ ($1 \le l \le r \le n$, $1 \le k \le m$)가 주어진다. 한 줄의 정수들은 공백으로 구분된다.

$q$개의 줄을 출력한다. 각 줄에는 해당 질의의 답을 정수 하나로 출력한다.