คำอธิบายโจทย์

JOI มีตราประทับ $3$ ชนิด ได้แก่ ตราประทับวงกลม ตราประทับกากบาท และตราประทับวงกลม-กากบาท ชนิดละตั้งแต่ $0$ อันขึ้นไป ตราประทับเหล่านี้สามารถใช้ปั๊มเครื่องหมายวงกลมหรือกากบาทลงบนกระดาษได้

เมื่อใช้ตราประทับวงกลมจะได้วงกลม $1$ อัน และเมื่อใช้ตราประทับกากบาทจะได้กากบาท $1$ อัน เมื่อใช้ตราประทับวงกลม-กากบาทจะได้วงกลม $1$ อันและกากบาท $1$ อันเรียงกันในแนวนอน โดยสามารถหมุนกลับทิศทางของตราประทับเพื่อให้กากบาทอยู่ทางขวาของวงกลม หรือให้วงกลมอยู่ทางขวาของกากบาทก็ได้

JOI ได้ใช้ตราประทับแต่ละอันที่ตนมีอยู่เพียงอันละ $1$ ครั้งพอดีตามลำดับที่เหมาะสม เพื่อปั๊มวงกลมและกากบาทเรียงเป็นแถวแนวนอนลงบนกระดาษ ลำดับของวงกลมและกากบาทที่ถูกปั๊มจะแทนด้วยสตริง $S$ โดยที่ $S$ เป็นสตริงความยาว $N$ ที่ประกอบด้วย O และ X หาก $S_i = $ O หมายความว่าเครื่องหมายลำดับที่ $i$ นับจากซ้ายที่ JOI ปั๊มคือวงกลม และหาก $S_i =$ X หมายความว่าเป็นกากบาท ($1 \le i \le N$)

คุณไม่ทราบจำนวนตราประทับที่ JOI มีอยู่ แต่คุณทราบลำดับของวงกลมและกากบาทที่ JOI ปั๊มออกมา จากลำดับของวงกลมและกากบาทที่ถูกปั๊ม จงหาค่ามากที่สุดที่เป็นไปได้ของจำนวนตราประทับวงกลม-กากบาทที่ JOI มีอยู่

ข้อจำกัด

• $1 \le N \le 100000 (= 10^5)$
• $S$ เป็นสตริงความยาว $N$
• ตัวอักษรแต่ละตัวของ $S$ คือ O หรือ X

ข้อมูลนำเข้าและส่งออก

ข้อมูลนำเข้า
ข้อมูลนำเข้าจะถูกกำหนดให้จากอินพุตมาตรฐานในรูปแบบต่อไปนี้:
$N$
$S$

ข้อมูลส่งออก
แสดงค่ามากที่สุดที่เป็นไปได้ของจำนวนตราประทับวงกลม-กากบาทที่ JOI มีอยู่

ตัวอย่างข้อมูลนำเข้าและส่งออก

ตัวอย่างข้อมูลนำเข้า 1

5
OXXOX

ตัวอย่างข้อมูลส่งออก 1

2

เครื่องหมายที่ JOI ปั๊มเรียงจากซ้ายไปขวาคือ วงกลม, กากบาท, กากบาท, วงกลม, กากบาท หากสมมติว่า JOI มีตราประทับวงกลม ตราประทับกากบาท และตราประทับวงกลม-กากบาทอยู่ $0, 1, 2$ อันตามลำดับ เขาจะสามารถปั๊มเครื่องหมายดังกล่าวนั้นได้โดยใช้ตราประทับตามลำดับต่อไปนี้:

• ใช้ตราประทับวงกลม-กากบาทอันที่ $1$ ปั๊มวงกลมและกากบาทตามลำดับนี้
• ทางขวาของสิ่งนี้ ใช้ตราประทับวงกลม-กากบาทอันที่ $2$ ปั๊มกากบาทและวงกลมตามลำดับนี้
• สุดท้าย ทางขวาของสิ่งนี้ ใช้ตราประทับกากบาทปั๊มกากบาท

เนื่องจากเป็นไปไม่ได้ที่จะมีตราประทับวงกลม-กากบาทตั้งแต่ $3$ อันขึ้นไป จึงแสดงผลเป็น $2$

ตัวอย่างข้อมูลนำเข้า 2

14
OXOXOXOXXOXOXO

ตัวอย่างข้อมูลส่งออก 2

7

ตัวอย่างข้อมูลนำเข้า 3

10
OOOOOOOOOO

ตัวอย่างข้อมูลส่งออก 3

0