Vào thời điểm 0 ban đầu, các bạn trong lớp học cô H đang xếp thành một hàng dài. Mỗi bạn trong lớp học đó đang quay mặt về 1 trong 2 phía : Trái hoặc Phải.

Để trấn chỉnh lớp học, cô H yêu cầu cả lớp “Nếu có hai học sinh liên tiếp quay mặt vào nhau thì ngay lập tức cả hai phải quay mặt lại (từ Trái thành Phải và ngược lại), động tác này làm trong 1s”. Hỏi sau bao nhiêu giây thì lớp cô H sẽ ngừng quay.

Lưu ý: Hai học sinh được coi là quay mặt vào nhau khi và chỉ khi học sinh bên trái đang quay mặt Phải và học sinh bên phải đang quay mặt Trái.

Đầu vào

Dòng 1: Số n (n<=10⁶) : Số học sinh

Dòng 2: một xâu kí tự độ dài n chỉ chứa kí tự L và R. Trong đó, kí tự thứ i là L thể hiện rằng học sinh thứ i quay mặt bên trái tại thời điểm ban đầu và ngược lại.

Đầu ra

Một dòng duy nhất là thơi gian để lớp cô H ngừng quay.

Ví Dụ