考點：離線+莫隊（Mo's Algorithm）

暴力解法：

對於一個範圍[l, r)的數據（我喜歡用0-based編號和左閉右開區間），我們開一個清單來記錄每個數分別出現幾次（當然編號要用0-based），此時詢問[l, r)的答案即是此清單中第一次出現0的位子。當然，因為一個有n個數的數列，其mex值絕對不會超過n，所以此清單長度開n + 1就夠了，而此時此清單中第一次出現0的位子，也可以表示為最小值出現的位子（如果最小值有多個，取最左邊的）。

優化：

找出上方所說清單中第一次出現0的位子，可以用線段樹實作，來取代每次暴力找。作法就是開一個和上方清單長度相同的最小值線段樹，如果上方所說清單中的某個位子是0，就將線段樹對應位子的值設為該位子的編號，不然將對應位子的值設為無限大，此時答案就是該線段樹的全域最小值。或是，上方清單長度可以改成開n就好（如果清單的前n項都不是0，那麼第(n + 1)項就自動為0）。但如此一來，前面所說「無限大」要改成n。利用此作法，可以很快的從[l, r)區間的答案推到[l - 1, r)、[l + 1, r)、[l, r - 1)、[l, r + 1)四個區間的答案（因為每次只需要更動線段樹上最多1個值，所以複雜度O(log n)）。然後反覆把所維護的區間進行擴張和收縮，並安排好一個處理詢問的順序，就可以快速獲得每個詢問的答案。
至於要怎麼安排好一個處理詢問的順序，我們當然不可能找到「最有效率」的順序，所以只要找到一個足夠有效率的順序，也就是擴張收縮的次數足夠小的順序即可。我們將每個詢問區間[l, r)想成是座標平面上的一個點（位於某個以(0, 0)為左下角，邊長為n的正方形內部或周界上），然後我們要將所有點進行排列，使相鄰二個點的曼哈頓距離總和足夠小。作法就是將這個長方形切成寬度是根號n的直條，然後同個直條的點按y座標由小而大排列，不同直條的點的連接，則按照左邊的直條的點要在最終序列的左邊為原則。
但要注意的是，處理詢問的時候，不能讓維護的區間的左界跑到右界右邊，所以從前一個詢問到下一個詢問，要先擴張再收縮。然後詢問最後是要按照初始給的順序輸出。

複雜度分析：

預處理時間：O(n + q log q)（大概吧，讀入數列與初始化線段樹所用的時間是O(n)，而莫隊將詢問排序所用的時間是O(q log q)，如果你有好好將詢問排序的話）
詢問時間：O(log n)/每次擴張收縮維護的區間，每個詢問所需擴張收縮維護的區間不固定，但整體擴張收縮的次數是好的
總時間：自己算
空間：O(n + q)（大概吧，線段樹所用的空間是O(n)，而莫隊將詢問排序所用的空間是O(q)）
AC（實測0.3s, 6.9MB）

常數優化：

1. 使用C++快讀快寫（網路上容易找到相關資料，我有使用）。
2. 線段樹的部分可以用迭代式線段樹，因為常數較小，而本題中線段樹只需使用建構、單點修改，以及查詢全域最小值（可以做到O(1)），所以只需實作那些功能。
3. 莫隊可以奇偶優化，期望複雜度的常數較小，就是上方安排詢問的處理順序，將正方形切成直條的部分，可以將第奇數個直條的點按y座標由大而小排，第偶數個直條的點的排序原則不變（或是反過來）。
4. 在必要的時候，也就是前一個要處理的詢問和下一個要處理的詢問完全沒交集的時候，大可將前面既有的資料全部打掉（或是也可以將維護的區間一步一步縮成空區間），然後再從零開始加入下一個要處理的詢問的相關資料。

註1：

本題有另一作法，可參考這裡。

註2：

本題解若有不清楚的部分，請隨時留言。