Packmen

Cho một dải ô gồm $n$ ô vuông được đánh số từ $1$ đến $n$. Mỗi ô có thể chứa một trong ba ký tự:

• P — có một Packman đứng ở ô đó.
• * — có một viên thức ăn ở ô đó.
• . — ô trống.

Mỗi đơn vị thời gian, mỗi Packman có thể di chuyển sang một ô kề bên (sang trái hoặc sang phải). Khi Packman đi vào một ô có thức ăn, nó ăn viên thức ăn đó ngay lập tức (không tốn thời gian). Một Packman được phép đổi hướng tùy ý nhiều lần nhưng không được rời khỏi dải. Nhiều Packman có thể đứng trên cùng một ô và không cản trở lẫn nhau.

Hãy tìm thời gian nhỏ nhất để tất cả các viên thức ăn đều bị ăn.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — độ dài của dải.
• Dòng thứ hai chứa xâu độ dài $n$ gồm các ký tự ., *, P mô tả dải ô.

Dữ liệu ra

• In ra một số nguyên duy nhất — thời gian nhỏ nhất cần thiết để ăn hết toàn bộ thức ăn.

Ràng buộc

• $2\le n\le {10}^5$.
• Đảm bảo có ít nhất một Packman và ít nhất một viên thức ăn.

Ví dụ