Trong lớp học của Tèo, mỗi bạn học sinh có một chiều cao nhất định. Tèo muốn thống kê thông tin về chiều cao của các bạn để phục vụ cho việc sắp xếp đội hình lớp. Cho danh sách chiều cao của \(n\) bạn học sinh và \(Q\) yêu cầu thống kê. Mỗi yêu cầu thuộc một trong hai loại:

• Loại 1: Đếm số lượng bạn học sinh có chiều cao lớn hơn hẳn giá trị \(H\).
• Loại 2: Đếm số lượng bạn học sinh có chiều cao nhỏ hơn hoặc bằng giá trị \(H\).

Hãy giúp Tèo thực hiện các yêu cầu trên.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(Q\) (\(n, Q \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) đại diện cho chiều cao của các bạn học sinh (\(a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(T\) và \(H\) (\(T \in \{1, 2\}, H \le 10^9\)) đại diện cho một truy vấn.

Output

• Với mỗi truy vấn, in ra một số nguyên duy nhất trên một dòng là kết quả tìm được.

Constraints

• Subtask 1 (\(30\%\) số điểm): \(n, Q \le 10^3\).
• Subtask 2 (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 3
150 160 170 160 180
1 160
2 160
1 180

2
3
0