Số cặp

Cho hai dãy gồm $n$ số nguyên, dãy thứ nhất gồm các số $a_1, a_2, \ldots, a_n$, dãy thứ hai gồm các số $b_1, b_2, \ldots, b_n$.

Yêu cầu: Hãy đếm số cặp chỉ số $(i, j)$ ($1 \le i \le j \le n$) mà số lớn nhất của các số $a_i, a_{i+1}, \ldots, a_j$ bằng số nhỏ nhất của các số $b_i, b_{i+1}, \ldots, b_j$.

Từ tệp văn bản pai.inp,

• Dòng đầu tiên chứa số nguyên $n$ ($1 \le n \le 10^5$);
• Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($1 \le |a_i| \le 10^9$);
• Dòng thứ ba chứa $n$ số nguyên $b_1, b_2, \ldots, b_n$ ($1 \le |b_i| \le 10^9$).

Các số trên một dòng của dữ liệu vào được ghi cách nhau bởi một dấu cách.

Ghi ra tệp văn bản pai.out,

• Một dòng duy nhất là kết quả của bài toán.

• Ràng buộc 1: 25% số test ứng với 25% số điểm của bài có $n \le 100$;
• Ràng buộc 2: 25% số test ứng với 25% số điểm của bài có $n \le 5000$;
• Ràng buộc 3: 25% số test ứng với 25% số điểm của bài có $n \le 10^5$; $a_1 \le a_2 \le \ldots \le a_n$; $b_1 \le b_2 \le \ldots \le b_n$;
• Ràng buộc 4: 25% số test còn lại ứng với 25% số điểm của bài không có ràng buộc gì thêm.