Truy vấn Tòa nhà Có thể thấy

Có $n$ tòa nhà xếp thành hàng. Một tòa nhà được gọi là có thể nhìn thấy (từ bên trái) nếu nó cao hơn tất cả các tòa nhà phía bên trái nó trong phạm vi xét. Xử lý $q$ truy vấn: mỗi truy vấn cho hai số $a,b$ — hỏi nếu chỉ có các tòa nhà từ $a$ đến $b$, thì có bao nhiêu tòa nhà có thể nhìn thấy?

Dữ liệu vào

• Dòng đầu: hai số nguyên $n$ và $q$.
• Dòng thứ hai: $n$ số nguyên $h_1,h_2,\dots ,h_n$ là chiều cao các tòa nhà.
• $q$ dòng tiếp theo: mỗi dòng chứa hai số $a$ và $b$.

Dữ liệu ra

Với mỗi truy vấn, in ra số tòa nhà có thể nhìn thấy trong đoạn $[a,b]$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le q\le 2\times {10}^5$
• $1\le h_i\le {10}^9$
• $1\le a\le b\le n$

Ví dụ