Chú lùn Nhân viên sở thú gần đây đã được thăng chức làm trưởng Khu nhà Cáo tại Sở thú Wrocław. Tình yêu của ông dành cho loài cáo (hay lis, như cách gọi trong tiếng Ba Lan) là vô bờ bến.

Chú lùn chăm sóc một hàng dài những con cáo trong các chuồng được bố trí dọc theo lối đi chính. Mỗi con cáo có một giá trị vẻ lộng lẫy, và chú lùn rất tự hào trong việc tìm ra Dãy con tăng dài nhất (LIS) theo vẻ lộng lẫy trong số những con cáo của mình.

Hôm nay, chú lùn đang chuyển một số con cáo đến các sở thú khác và thay thế chúng bằng những con cáo mà các sở thú khác gửi lại. Vào đầu ngày, Chú lùn Nhân viên sở thú đứng cùng một xe đẩy chở những con cáo mới bên cạnh chuồng đầu tiên (ngoài cùng bên trái). Chú lùn sẽ đi bộ dọc theo lối đi, di chuyển từ chuồng này sang chuồng khác. Đôi khi, ông sẽ dừng lại ở một trong các chuồng và thay thế con cáo ở đó bằng một con cáo khác, có thể có vẻ lộng lẫy khác. Mỗi lần điều này xảy ra, ông phải tính toán ngay lập tức độ dài của dãy con có vẻ lộng lẫy tăng dài nhất. Bạn có thể giúp ông theo dõi con số này không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $N$ và $Q$, biểu thị số lượng chuồng dọc theo lối đi và số lượng hành động mà chú lùn thực hiện.

Dòng thứ hai của dữ liệu vào chứa $N$ số nguyên $m_1, m_2, \dots, m_N$, mô tả vẻ lộng lẫy ban đầu của mỗi con cáo.

$Q$ dòng tiếp theo mô tả các hành động. Một hành động đơn lẻ là một trong các loại sau:

1. < — chú lùn di chuyển sang trái một chuồng,
2. > — chú lùn di chuyển sang phải một chuồng,
3. ! v — chú lùn đổi con cáo trong chuồng hiện tại lấy một con cáo có vẻ lộng lẫy là $v$.

Kết quả

Với mỗi hành động !, hãy in ra một dòng duy nhất chứa độ dài của dãy con tăng dài nhất theo vẻ lộng lẫy của những con cáo.

Giới hạn

$2 \le N \le 200\,000$, $1 \le Q \le 500\,000$, $1 \le m_i \le 10^6$, $1 \le v \le 10^6$.

Ví dụ

Dữ liệu vào 1

5 8
3 4 1 7 2
>
! 2
>
>
>
! 10
<
! 11

Kết quả 1

2
3
2

Giải thích

Đầu tiên, Chú lùn Nhân viên sở thú di chuyển đến chuồng thứ hai và đổi con cáo lấy một con có vẻ lộng lẫy $2$. Độ dài của dãy con tăng dài nhất là $2$. Sau đó ông di chuyển đến chuồng thứ năm và đổi con cáo lấy một con có vẻ lộng lẫy $10$, và độ dài của LIS trở thành $3$. Cuối cùng, Nhân viên sở thú di chuyển đến chuồng thứ tư và đổi vẻ lộng lẫy thành $11$, làm cho độ dài của LIS trở lại thành $2$.