Có \(n\) tòa nhà trên một hàng, được đánh số \(1, 2,\dots, n\) từ trái sang phải. Bạn đang đứng bên trái tòa nhà đầu tiên. Bạn có thể nhìn thấy một tòa nhà nếu nó cao hơn tất cả các tòa nhà ở bên trái nó.

Nhiệm vụ của bạn là xử lý \(q\) truy vấn: Nếu chỉ các tòa nhà trong đoạn \([a, b]\) tồn tại, bạn sẽ nhìn thấy bao nhiêu tòa nhà?

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\): số tòa nhà và số truy vấn.

Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2, \dots, h_n\): độ cao của các tòa nhà.

Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng chứa hai số nguyên \(a\) và \(b\).

Output

Với mỗi truy vấn, in một số nguyên: số tòa nhà nhìn thấy được.

Constraints

• \(1 \le n \le 10^5\)

• \(1 \le q \le 2 \cdot 10^5\)

• \(1 \le h_i \le 10^9\)

• \(1 \le a \le b \le n\)

Example

5 3
4 1 2 2 3
1 5
2 5
3 4

1
3
1