# 猩猩相惜 🦍
在天文台工作的文文喜歡看星星，也喜歡看動物園裡的猩猩。但是隨著地球環境日漸被人類所破壞，地球上猩猩的棲息環境也遭到人類的迫害。對猩猩惺惺相惜的文文於是決定為地球上的猩猩們找尋一個適合猩猩生存的星星。

然而這個星星可不能只是適合猩猩生存的星星，還必須與地球越近越好，最好選擇與地球相鄰的星系，這樣時時心繫猩猩星星的文文才能時不時探訪。於是文文對天空中的所有待選星星進行比較，透過一個特殊函數 🦍(⭐️) — 猩猩函數 來對其評分，其中得到越高猩猩分數的星星就越適合作為最後的猩之所向。但是也不能選擇擁有過高的猩猩分數的星星，因為通常這種星星會離地球太近，導致地球上的盜獵者太容易找到文文心愛的猩猩們。

先在輪到你來幫文文忙了，文文已經幫天空中的$n$ 顆星星進行 🦍 函數的評分並排序，如 $a_1,a_2,…,a_n$，現在請你對於文文的每個 $(l,r)$ 提問，求出有多少不同的$i$使得 $l≤a_i<r$，幫幫文文找到他心目中的超猩星吧！

### 輸入說明
每筆測資第一行有兩個正整數 $n,q,(1≤n,q≤10^5)$, 分別代表總共有 $n$ 顆星球與 $q$ 筆詢問。
接下來有一行長度為 $n$ 且已從小到大排序後的正整數數列 $a_1,a_2,…,a_n,∀i∈[1,n]:0≤a_i<2^{31}$。
接著是 $q$ 行每行包含兩個正整數 $l,r,(0≤l≤r<2^{31})$ 的詢問。

### 輸出說明
請對每筆詢問輸出一行包含一個正整數 $k$ 代表有多少不同的 $i$ 滿足 $l≤a_i<r$。

### 範例測資
#### 輸入

3 6
145522007 755486867 2126437348 
1789916740 1933517952
206332615 1966544051
1337176761 1449817181
286000222 2141107887
1179051608 1799722592
2069218500 2071865745

### 輸出

0
1
0
2
0
0

### 注意事項
請試圖找到比直接搜尋更快的作法，naïve 解會得到 **Time Limit Exeed** 並只能得到 20% 的總分。
請勿 `#include <algorithm>`，否則你將得到 **Compile Error**。
請注意邊界狀況，如：當要搜尋第一個小於 $x$ 的 $a_i$ 時，若 $∀i:a_i≥x$，則你的程式可能會發生什麼問題。
# Code

#include <iostream>
using namespace std;
int target[100005] = {}, guess[3] = {}, ans[3] = {};

int Less(int target_num, int guess_num)
{
  if (target[target_num] >= guess[guess_num])
  {
    return 1;
  } 
  else 
  {
    return 0;
  }
}

int main()
{
  int n, q;
  cin >> n >> q;

  for (int i = 0; i < n; i++)
  {
    cin >> target[i];
  }

  for (int i = 0; i < q; i++)
  {
    cin >> guess[0] >> guess[1];
    for (int t = 0; t < 2; t++)
    {
      int min_num = 0, max_num = n, guess_num = 0, mi = 0, ma = 0;
      while (true)
      {
        guess_num = (max_num + min_num) / 2;
        //cout << "\"" << guess_num << "\"";
        mi = Less(guess_num, t);
        ma = Less(guess_num + 1, t);
        if (guess_num == n)
        {
          ans[t] = n - 1;
          break;
        }
        
        if (mi == 0 && ma == 1)
        {
          ans[t] = guess_num;
          break;
        }
        if (mi == 1)
        {
          if (guess_num == 0)
          {
            ans[t] = -1;
            break;
          }
          
          max_num = guess_num - 1;
        }
        else
        {
          min_num = guess_num + 1;
        }
      }
      //cout << "\n";
    }
    cout << ans[1] - ans[0] << "\n";
  }
  
      
}