Phú ông có ~n~ con bò, mỗi con được gán một chỉ số id từ ~1~ đến ~n~. Con bò có chỉ số ~id~ mang mã giống ~a[id]~. Ban đầu, các con bò xếp theo thứ tự từ ~id = 1~ đến ~id = n~. Phú ông muốn chụp một bức ảnh gồm một số con bò liên tiếp để gửi tham dự cuộc thi Hoa hậu bò. Trước khi chụp ảnh, ông thực hiện ~m~ lần đổi chỗ các con bò theo các thao tác:

A i j: con bò có chỉ số id = ~i~ được chuyển sang đứng bên trái con bò có id = ~j~.

B i j: con bò có chỉ số id = ~i~ được chuyển sang đứng bên phải con bò có id = ~j~.

Sau khi thực hiện đủ ~m~ lượt đổi chỗ, ông muốn tìm một đoạn liên tiếp từ vị trí ~L~ đến ~R~ sao cho trong đoạn này, mỗi mã giống xuất hiện ít nhất một lần.

Chi phí của bức ảnh = ~R - L + 1~ (độ rộng của đoạn).
Yêu cầu: Tìm chi phí nhỏ nhất.

Dữ liệu vào (CPHOTO.INP)

Dòng 1: hai số nguyên ~n, m~ ~(1 ≤ n, m ≤ 10^5)~

Dòng 2: ~n~ số nguyên ~a_1, a_2, …, a_n~ ~(1 ≤ a_i ≤ 10^5)~

~m~ dòng tiếp theo: mỗi dòng mô tả phép đổi với định dạng ~A~ ~i~ ~j~ hoặc ~B~ ~i~ ~j~ ~(1 ≤ i, j ≤ n) ~

Kết quả ra (CPHOTO.OUT)

Một số nguyên duy nhất — chi phí nhỏ nhất tìm được.

Ví dụ:

CPHOTO.INP

6 3
1 4 1 2 4 1
A 1 3
B 4 2
B 6 1

CPHOTO.OUT

3

Giải thích:

Sau khi đổi, dãy mã giống cuối cùng: ~4 2 1 1 1 4~.
Đoạn ngắn nhất chứa đủ các giống là ~4 2 1~ (hoặc ~2 1 1 1 4~) có độ dài ~3~.

Ràng buộc chấm điểm

Subtask 1 (40%): ~m = 1~,

Subtask 2 (30%): ~1 ≤ n, m ≤ 1000~,

Subtask 3 (30%): không có ràng buộc thêm.