Problem: Range Count Query

Given the sequence a_1, a_2, .., a_N.

In the query, answer the number of terms whose value is l or more and r or less.

input


N Q
a_1 a_2 ... a_N
l_1 r_1
l_2 r_2
::
l_q r_q


output


ans_1
ans_2
::
ans_q


On line i, output the answer to the i-th query, that is, the number of j such as l_i \ leq a_j \ leq r_i.

Constraint

* 1 \ leq N, Q \ leq 10 ^ 5
* 1 \ leq a_i \ leq 10 ^ 9
* 1 \ leq l_i \ leq r_i \ leq 10 ^ 9



Input example


6 3
8 6 9 1 2 1
2 8
1 7
3 5


Output example


3
Four
0






Example

Input

6 3
8 6 9 1 2 1
2 8
1 7
3 5


Output

3
4
0

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

#define REP(i, a) for(int64 i = 0; i < (a);i++)
#define FOR(i, a, b) for(int64 i = (a); i < (b); i++)
#define INF (int64)1e9
#define INF_LL (int64)1e18
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int32_t;
using int64 = int64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

template<typename A, typename B> inline void chmin(A &a, B b) { if (a > b) a = b;}
template<typename A, typename B> inline void chmax(A &a, B b) { if (a > b) a = b;}

template<typename CommutativeMonoid>
class FenwickTree{
public:
  using value_structure = CommutativeMonoid;
  using value_type = typename CommutativeMonoid::value_type;
  using size_type = ::std::size_t;

private:
  ::std::vector<value_type> tree;
  size_type N;

  static value_type calc(const value_type& a, const value_type& b){
    return value_structure::operation(a, b);
  }

public:
  FenwickTree(){}
  FenwickTree(const size_type& N):N(N+10), tree(N+11, value_structure::identity()){}
  FenwickTree(const FenwickTree& bit):tree(bit.tree), N(bit.N){}

  void update(size_type k, const value_type& diff){ // update k in [1, N]
    for(;k <= N;k += k & -k){
      tree[k] = calc(tree[k], diff);
    }
  }

  value_type query(size_type k) const { // sum of [1, k]
    value_type res = value_structure::identity();
    for(;k > 0;k -= k & -k){
      res = calc(res, tree[k]);
    }
    return res;
  }

  void updatez(size_type k, value_type v){ // 0-indexed
    update(k+1, v);
  }

  value_type queryz(size_type k) const { // [0, k)
    return query(k);
  }

  size_type search(const std::function<bool(value_type)>& f) const { // Find k :[0, k) -> True, [0, k-1) -> False
    if(f(value_structure::identity()))
      return 0;
    if(!f(query(N)))
      return N+1;
    value_type x = value_structure::identity();
    size_type k = 1, idx = 0;
    while(k <= N) k <<= 1;
    k >>= 1;
    for(;k > 0;k >>= 1){
      if((idx|k) <= N && !f(tree[idx|k]+x))
        x = calc(x, tree[idx |= x]);
    }
    return idx+1;
  }

  size_type size() const {return N;}
};

class v_monoid {
public:
  using value_type = int64;
  static const value_type identity() { return 0; }
  static const value_type operation(const value_type& a, const value_type& b) {
    return a + b;
  }
};

int main(void) {
  int64 N, Q;
  cin >> N >> Q;
  vector<int64> A(N);
  REP(i, N) cin >> A[i];
  sort(all(A));
  REP(i, Q) {
    int64 l, r;
    cin >> l >> r;
    cout << upper_bound(all(A), r) - lower_bound(all(A), l)  << endl;
  }
}