Một cặp số $(l,r)$ được gọi là cặp số đầy đủ khi và chỉ khi $min(a_l\rightarrow a_r)=l$ và $max(a_l\rightarrow a_r)=r$

Dựa vào nhận xét trên, ta có thể kiểm tra tất cả cặp số trong $O(n^2)$. Sau đó, kết hợp quy hoạch động hoặc mảng tổng dồn để xuất kết quả trong $O(1)$

Độ phức tạp: $O(n^2)$

Đây rõ ràng là một bài toán đếm số lượng cặp số đầy đủ của cả dãy.

Đầu tiên ta gọi $lmax_i,rmax_i$ là giá trị đầu và cuối thỏa mãn với mọi $lmax_i\le j\le rmax_i$ thì $max(a_j\rightarrow a_i)=i$ ($1\le lmax_i\le rmax_i\le i$). Trường hợp không có giá trị $j$ nào thỏa mãn thì $lmax_i=rmax_i=-1$
Ta cũng gọi $lmin_i,rmin_i$ là giá trị đầu và cuối thỏa mãn với mọi $lmin_i\le j\le rmin_i$ thì $min(a_i\rightarrow a_j)=i$ ($i\le lmin_i\le rmin_i\le n$). Trường hợp không có giá trị $j$ nào thỏa mãn thì $lmin_i=rmin_i=-1$

Hướng tiếp cận của chúng ta sẽ là với mọi $i$ ta sẽ kiểm tra mọi giá trị $j$ từ $lmin_i\rightarrow rmin_i$, nếu $lmax_j\le i\le rmax_j$ thì tăng biến kết quả lên $1$

Về việc tìm $lmax_i,rmax_i,lmin_i,rmin_i$, ta có thể chặt nhị phân kết hợp sử dụng sparse table để tìm giá trị trong $O(log(n))$

Để đếm nhanh số khả năng thỏa mãn khi xét từng giá trị $i$, ta có thể sử dụng chia căn để giải quyết trong $O(\sqrt n)$

Độ phức tạp: $O(n\cdot \sqrt n)$

Ta cải tiến từ subtask 2, thay vì đếm, ta sẽ gọi $shift_i$ là giá trị $j$ nhỏ nhất thỏa mãn $lmin_i\le j\le rmin_i$ và $lmax_j\le i\le rmax_j$. Việc này có thể giải quyết trong $O(\sqrt n)$

Hướng tiếp cận của chúng ta là sẽ "đẩy" mảng, tức là nếu cặp số $(i,j)$ và $(j+1,k)$ đều là cặp số đầy đủ thì $(i,k)$ cũng là cặp số đầy đủ

Ý tưởng là ta sẽ chia các phần tử $i,shift_i+1,shift_{shift_i+1}+1,\dots$ vào cùng 1 nhóm sau đó sử dụng công thức để tính nhanh.

Gọi $F_i$ là chỉ số nhóm của phần tử thứ $i$ sau khi đã chia ($1\le i\le n+1$). Chỉ số nhóm có thể đánh dấu từ $1$ đến $n+1$.

Từ ý tưởng, ta có thể chuyển bài toán về dạng: Tính $\sum_{i = 1}^{n+1} \frac{cnt_i\cdot (cnt_i-1)}2$ với $cnt_i$ là số lần xuất hiện giá trị $i$ của mảng $F$ khi xét các phần tử nằm trong đoạn $[l,r+1]$

Đây là một bài chia căn khá là cơ bản, có thể sử dụng Mo's algorithm để sắp xếp truy vấn xong giải quyết tất cả trong $O(q\cdot \sqrt n)$

Độ phức tạp: $O((n+q)\cdot \sqrt n)$