Swapping Seats

Υπάρχουν ~N~ άνθρωποι καθισμένοι σε ένα κυκλικό τραπέζι για μια πολύωρη συνεδρίαση διαπραγματεύσεων. Κάθε άτομο ανήκει σε μία από τις τρεις ομάδες: ~A~, ~B~, ~C~. Μια ομάδα είναι χαρουμένη αν όλα τα μέλη της κάθονται δίπλα το ένα στο άλλο, σε ένα μπλοκ διαδοχικών θέσεων. Θα θέλατε να κάνετε όλες τις ομάδες χαρούμενες μέσω κάποιας ακολουθίας ανταλλαγών. Σε κάθε εκτέλεση μιας ανταλλαγής, δύο άτομα ανταλλάσσουν θέσεις μεταξύ τους. Ποιος είναι ο ελάχιστος αριθμός ανταλλαγών που απαιτείται για να γίνουν όλες οι ομάδες χαρούμενες;

Είσοδος

Η είσοδος θα αποτελείται από μία γραμμή που θα περιέχει ~N\;(1 \le N \le 1\;000\;000)~ χαρακτήρες, όπου κάθε χαρακτήρας θα είναι ~A~, ~B~ ή ~C~. Ο ~i~-οστός χαρακτήρας δηλώνει την ομάδα του ατόμου που κάθεται αρχικά στην ~i~-οστή θέση στο τραπέζι, όπου οι θέσεις αριθμούνται κατά τη φορά των δεικτών του ρολογιού.

Για ~4~ από τους ~15~ διαθέσιμους βαθμούς, η είσοδος δεν θα περιέχει χαρακτήρες ~C~ και ~N \le 5000~.

Για επιπλέον ~4~ από τους ~15~ διαθέσιμους βαθμούς, η είσοδος δεν θα περιέχει χαρακτήρες ~C~.

Για επιπλέον ~4~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 5000~.

Έξοδος

Εξάγετε έναν ακέραιο αριθμό, τον ελάχιστο δυνατό αριθμό ανταλλαγών.

Παράδειγμα

input

BABCBCACCA

output

2

Επεξήγηση του παραδείγματος:

Σε μια πιθανή ακολουθία, η πρώτη ανταλλαγή οδηγεί στη διάταξη καθισμάτων: ~AABCBCBCBCCA~. Μετά τη δεύτερη ανταλλαγή, η διάταξη είναι ~AABBBCCCCA~.