提示: 欢迎访问OurACM平台。
Problem 2072 Count

Accept: 173    Submit: 527
Time Limit: 1000 mSec    Memory Limit : 65536 KB

Problem Description

Given an array of positive integers and m queries.Each query contains i, j, x, output the number of occurrences of x into the subarray Ai,Ai+1...,Aj.

Input

There are several cases. The first line of each case contains tow integers n, q(1<=n,q<=100000), indicating the array length and the number of queries.The second line contains n positive integers ai(1 <= ai <= 100000).Next q lines contain three positive integers i,j,x(1<=i<=j<=n).

Output

For each query output one line, the number of occurrences of x.

Sample Input

3 2 1 2 1 1 2 1 1 3 1

Sample Output

1 2

Source

FOJ有奖月赛-2012年3月

Submit  Back  Status  Discuss