Nhân dịp kỷ niệm \(101\) năm thành lập, hãng sản xuất con dấu IOI mở dịch vụ làm con dấu chứa những thông điệp dài theo yêu cầu. Hãng đã phát triển loại con dấu cho phép chèn, xóa hoặc thay thế từng ký tự bằng thao tác thủ công.

Thông điệp chỉ gồm hai chữ cái I và O. Trước hết, hãng dùng máy để tạo một con dấu có độ dài ít nhất \(1\). Do đặc tính của máy, chuỗi ký tự tạo ra phải bắt đầu và kết thúc bằng I, đồng thời hai ký tự liên tiếp bất kỳ phải khác nhau. Chẳng hạn, máy có thể tạo I, IOI hoặc IOIOIOI.

Việc tạo con dấu bằng máy không tốn thời gian. Sau đó, có thể thực hiện các thao tác sau, mỗi thao tác tốn \(1\) giây:

• Chèn một ký tự vào một vị trí bất kỳ, kể cả đầu hoặc cuối chuỗi.
• Xóa một ký tự.
• Thay một ký tự bằng ký tự còn lại.

Ví dụ, từ IOIOIOI, thay ký tự thứ \(3\) bằng O, rồi chèn một chữ O vào giữa ký tự thứ \(5\) và thứ \(6\) của chuỗi vừa thu được, sẽ tạo thành IOOOIOOI trong \(2\) giây.

Yêu cầu

Cho thông điệp cần tạo, hãy tìm tổng thời gian chỉnh sửa nhỏ nhất. Trong các cách đạt thời gian nhỏ nhất đó, hãy tìm độ dài nhỏ nhất của con dấu ban đầu được tạo bằng máy.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng thứ nhất chứa số nguyên \(N\), là độ dài thông điệp.
• Dòng thứ hai chứa chuỗi \(S\) gồm \(N\) ký tự I hoặc O, là thông điệp cần tạo.

Dữ liệu ra

Ghi ra đầu ra chuẩn:

• Dòng thứ nhất chứa thời gian chỉnh sửa nhỏ nhất, tính bằng giây.
• Dòng thứ hai chứa độ dài nhỏ nhất của con dấu ban đầu trong các cách đạt thời gian đó.

Ràng buộc

• \(1\le N\le1\,000\,000\).
• \(S\) chỉ gồm hai ký tự I và O.
• Giới hạn thời gian: \(1\) giây cho mỗi test; giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Tổng điểm là \(100\), gồm \(25\) nhóm, mỗi nhóm \(4\) điểm và chứa đúng một test, lần lượt từ 01 đến 25.

Các test thỏa mãn \(N\le5000\) chiếm \(40\) điểm.

Ví dụ

8
IOOOIOOI

2
7

5
IOIOI

0
5

5
IIIII

2
5