Dna

Οι βιολόγοι ανακάλυψαν ένα παράξενο μόριο DNA, το οποίο περιγράφεται καλύτερα ως μια ακολουθία ~N~ χαρακτήρων από το σύνολο ~{A,\;B}~. Μια απίθανη αλληλουχία μεταλλάξεων έχει οδηγήσει σε έναν κλώνο DNA που αποτελείται μόνο από χαρακτήρες ~A~ .
Οι βιολόγοι το βρήκαν πολύ περίεργο, έτσι άρχισαν να μελετούν τις μεταλλάξεις με μεγαλύτερη λεπτομέρεια.

Ανακάλυψαν δύο τύπους μεταλλάξεων. Ένας τύπος έχει ως αποτέλεσμα την αλλαγή ενός μεμονωμένου χαρακτήρα της ακολουθίας (~A \rightarrow B~ ή ~B \rightarrow A~). Ο δεύτερος τύπος αλλάζει ένα ολόκληρο πρόθεμα της ακολουθίας, αντικαθιστώντας συγκεκριμένα όλους τους χαρακτήρες σε θέσεις από το ~1~ έως το ~K~ (για κάποιους ~K~ μεταξύ ~1~ και ~N~, συμπεριλαμβανομένων αυτών) με τον άλλο χαρακτήρα (~A~ με ~B~, ~B~ με ~A~).

Υπολογίστε τον ελάχιστο δυνατό αριθμό μεταλλάξεων που θα μπορούσαν να μετατρέψουν το αρχικό μόριο στην τελική του κατάσταση (που περιέχει μόνο χαρακτήρες ~A~). Οι μεταλλάξεις μπορούν να συμβούν με οποιαδήποτε σειρά.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~N\;(1 \leq N \leq 1\,000\,000)~, το μήκος του μορίου.

Η δεύτερη γραμμή εισόδου περιέχει μια συμβολοσειρά με ~N~ χαρακτήρες, με κάθε χαρακτήρα να είναι είτε ~A~ είτε ~B~.
Αυτή η συμβολοσειρά αντιπροσωπεύει την αρχική κατάσταση του μορίου.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο ελάχιστο αριθμό μεταλλάξεων.

Παραδείγματα

input

4
ABBA

output

2

input

5
BBABB

output

2

input

12
AAABBBAAABBB

output

4