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:
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
const int INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
const ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans, a[ohara], b, c, d, tmp, m, h, w, x, y, sum[ohara], k, q,
    l[ohara], r[ohara];

template <class T>
vector<ll> Zarts(const vector<T> &AR, ll CNT = 0) {
  vector<ll> RES;
  map<T, ll> MP;
  for (auto &e : AR) MP[e] = 0;
  for (auto &e : MP) e.se = CNT++;
  for (auto &e : AR) {
    // fukugen[MP[e]] = e;
    RES.push_back(MP[e]);
  }
  return RES;
}

int main(void) {
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> q;
  V a_in(n + 2 * q + 1);
  ll now = 0;
  rep(i, n) cin >> a_in[now++];
  rep(i, q) {
    cin >> a_in[now] >> a_in[now + q];
    now++;
  }
  auto af = Zarts<ll>(a_in);
  now = 0;
  rep(i, n) a[i] = af[now++];
  rep(i, q) {
    l[i] = af[now];
    r[i] = af[now + q];
    now++;
  }

  rep(i, n) sum[a[i]]++;
  rrep(i, 1, ohara) sum[i] += sum[i - 1];
  rep(i, q) { Cout(sum[r[i]] - sum[l[i] - 1]); }
  return 0;
}