Kurcaci Sang Penjaga Kebun Binatang baru-baru ini dipromosikan menjadi kepala Paviliun Rubah di Kebun Binatang Wrocław. Kecintaannya pada rubah (atau lis, begitu sebutannya dalam bahasa Polandia) tidak mengenal batas.

Sang kurcaci merawat barisan panjang rubah di dalam kandang-kandang yang disusun di sepanjang jalur utama. Setiap rubah memiliki nilai keagungan, dan sang kurcaci merasa bangga dalam menemukan Upabarisan Naik Terpanjang (LIS) dari nilai keagungan di antara rubah-rubahnya.

Hari ini, sang kurcaci memindahkan beberapa rubah ke kebun binatang lain dan menggantinya dengan rubah-rubah yang dikirimkan oleh kebun binatang lain sebagai gantinya. Di awal hari, Kurcaci Sang Penjaga Kebun Binatang berdiri dengan kereta berisi rubah-rubah baru di sebelah kandang pertama (paling kiri). Sang kurcaci akan berjalan di sepanjang jalur, berpindah dari kandang ke kandang. Terkadang, ia akan berhenti di salah satu kandang dan mengganti rubah di sana dengan rubah lain, yang mungkin memiliki keagungan berbeda. Setiap kali hal ini terjadi, ia harus segera menghitung panjang dari upabarisan keagungan naik terpanjang. Bisakah Anda membantunya melacak angka ini?

Masukan

Baris pertama masukan berisi dua bilangan bulat $N$ dan $Q$, yang menyatakan jumlah kandang di sepanjang jalur dan jumlah tindakan yang dilakukan sang kurcaci.

Baris kedua masukan berisi $N$ bilangan bulat $m_1, m_2, \dots, m_N$, yang menjelaskan keagungan awal dari setiap rubah.

$Q$ baris berikutnya menjelaskan tindakan-tindakan tersebut. Satu tindakan adalah salah satu dari berikut ini:

1. < — sang kurcaci berpindah satu kandang ke kiri,
2. > — sang kurcaci berpindah satu kandang ke kanan,
3. ! v — sang kurcaci menukar rubah di kandang saat ini dengan seekor rubah dengan keagungan $v$.

Keluaran

Untuk setiap tindakan !, keluarkan satu baris yang berisi panjang dari upabarisan naik terpanjang dari keagungan rubah-rubah tersebut.

Batasan

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

Contoh

Masukan 1

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

Keluaran 1

2
3
2

Catatan

Pertama, Kurcaci Sang Penjaga Kebun Binatang berpindah ke kandang kedua dan menukar rubah dengan rubah yang memiliki keagungan $2$. Panjang upabarisan naik terpanjang adalah $2$. Kemudian ia berpindah ke kandang kelima dan menukar rubah dengan rubah yang memiliki keagungan $10$, dan panjang LIS menjadi $3$. Terakhir, Sang Penjaga Kebun Binatang berpindah ke kandang keempat dan mengubah keagungannya menjadi $11$, membuat panjang LIS kembali menjadi $2$.