輸入第一行包含一個(gè)整數(shù) n 表示數(shù)列長度。

第二行包含 n 個(gè)整數(shù) a₁, a₂, · · · , a_n，表示數(shù)列中的數(shù)。

第三行包含一個(gè)整數(shù) m 表示詢問次數(shù)。

接下來 m 行描述詢問，其中第 i 行包含三個(gè)整數(shù) l_i ,r_i , k_i 表示詢問 [l_i ,r_i ] 區(qū)間內(nèi)有多少數(shù)出現(xiàn)了 k_i 次。

3
1 2 2
5
1 1 1
1 1 2
1 2 1
1 2 2
1 3 2

1
0
2
0
1

對(duì)于 20% 的評(píng)測(cè)用例，n, m ≤ 500, 1 ≤ a₁, a₂, · · · , a_n ≤ 1000；

對(duì)于 40% 的評(píng)測(cè)用例，n, m ≤ 5000；

對(duì)于所有評(píng)測(cè)用例，1 ≤ n, m ≤ 100000, 1 ≤ a₁, a₂, · · · , a_n ≤ 100000, 1 ≤ l_i ≤ r_i ≤ n, 1 ≤ k_i ≤ n。