사육사 드워프는 최근 브로츠와프 동물원의 여우관 관장으로 승진했습니다. 여우(폴란드어로는 lis라고 부릅니다)에 대한 그의 사랑은 끝이 없습니다.

드워프는 주 산책로를 따라 늘어선 우리에 있는 긴 줄의 여우들을 돌보고 있습니다. 각 여우에게는 화려함(magnificence) 수치가 있으며, 드워프는 자신의 여우들 중에서 화려함의 최장 증가 부분 수열(LIS)을 찾는 것에 자부심을 느낍니다.

오늘 드워프는 일부 여우를 다른 동물원으로 보내고, 다른 동물원에서 대신 보내온 여우들로 교체하고 있습니다. 하루가 시작될 때, 사육사 드워프는 새로운 여우들이 실린 수레를 끌고 첫 번째(가장 왼쪽) 우리 옆에 서 있습니다. 드워프는 산책로를 따라 걸으며 우리에서 우리로 이동합니다. 때때로 그는 어느 한 우리에 멈춰 서서 거기에 있는 여우를 화려함이 다를 수 있는 다른 여우로 교체합니다. 이 일이 일어날 때마다 그는 즉시 가장 긴 증가하는 화려함 부분 수열의 길이를 계산해야 합니다. 그가 이 숫자를 계속 추적할 수 있도록 도와주겠습니까?

입력

입력의 첫 번째 줄에는 산책로를 따라 있는 우리의 수와 드워프가 취하는 행동의 수를 나타내는 두 정수 $N$과 $Q$가 주어집니다.

입력의 두 번째 줄에는 각 여우의 초기 화려함을 설명하는 $N$개의 정수 $m_1, m_2, \dots, m_N$이 주어집니다.

다음 $Q$개의 줄에는 행동이 설명됩니다. 하나의 행동은 다음 중 하나입니다:

1. < — 드워프가 왼쪽으로 한 우리 이동합니다,
2. > — 드워프가 오른쪽으로 한 우리 이동합니다,
3. ! v — 드워프가 현재 우리에 있는 여우를 화려함이 $v$인 여우로 교환합니다.

출력

각 ! 행동마다 여우들의 화려함의 최장 증가 부분 수열의 길이를 한 줄에 출력합니다.

제한

$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$.

예제

예제 입력 1

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

예제 출력 1

2
3
2

노트

먼저 사육사 드워프는 두 번째 우리로 이동하여 여우를 화려함이 $2$인 여우로 교환합니다. 이때 최장 증가 부분 수열의 길이는 $2$입니다. 그런 다음 다섯 번째 우리로 이동하여 여우를 화려함이 $10$인 여우로 교환하면 LIS의 길이는 $3$이 됩니다. 마지막으로 사육사가 네 번째 우리로 이동하여 화려함을 $11$로 바꾸면 LIS의 길이는 다시 $2$가 됩니다.