Đầu tiên, ta đi xây dựng mảng ~L[i]~ có nghĩa là vị trí lớn nhất thỏa mãn ~L[i] < i~ và ~a[L[i]] = a[i]~, nếu không có thì ~L[i] = 0~. Tương tự ta có ~R[i]~ là vị trí nhỏ nhất thỏa mãn ~R[i] > i~ và ~a[R[i]] = a[i]~, nếu không có thì ~R[i] = n + 1~.

Ta có:

- Hàm ~\text{getMax}(l,r) = (\max (L[i])~ với ~i \in [l,r])~

- Hàm ~\text{getMin}(l,r) = (\min (R[i])~ với ~i \in [l,r])~

- Ta rút ra được nhận xét rằng, một đoạn ~[l,r]~ là phân biệt khi và chỉ khi ~\text{getMin}(l,r) > r~ và ~\text{getMax}(l,r) < l~.

Như vậy, với mỗi truy vấn có dạng ~[l,r]~, ta sẽ làm như sau:

- Tìm vị trí ~posL > l~ nhỏ nhất thỏa mãn ~\text{getMax}(posL,r) < mid~. Nếu không tìm được hoặc ~\text{getMin}(l,posL-1) \le posL-1~ thì trả kết quả về 0. Nói cách khác, ta đang tìm vị trí ~posL~ lớn nhất thỏa mãn đoạn ~[posL,r]~ phân biệt. Vậy nên, nếu ta không tìm thấy ~posL~ hoặc đoạn ~[l,posL-1]~ không phải là dãy số phân biệt, sẽ chẳng có cách nào chia dãy ra làm ~2~ để thỏa mãn điều kiện cả.

- Tương tự tìm vị trí ~posR< r~ lớn nhất thỏa mãn ~\text{getMin}(l,posR) > mid~. Nếu không tìm được hoặc ~\text{getMax}(posR+1,r) \ge posR+1~ thì trả kết quả về ~0~.

- Để có thể tối ưu thuật toán, ta sẽ áp dụng thuật toán chặt nhị phân kết quả để tìm ~posL~ và ~posR~, kèm với đó ta sử dụng sparse table để tính các hàm ~\text{getMin}~ và ~\text{getMax}~ trong ~O(1)~.

- Nếu ta tìm được cả ~posL~ và ~posR~, có thể thấy ~posR \ge posL~, và với đoạn ~[posL,posR]~, ta có thể lấy bất kì vị trí nào để chia dãy làm ~2~ mà vẫn thỏa mãn điều kiện đề bài. Sẽ có ~posR - posL + 2~ cách chia như vậy.

- Tổng kết lại, với mỗi truy vấn, ta sẽ chỉ mất ~O(\log n)~ để giải quyết.

Độ phức tạp: ~O((n + q) \log n)~