Arranging Books

Η Βαλεντίνα θέλει τα βιβλία να είναι τοποθετημένα στα ράφια με έναν συγκεκριμένο τρόπο. Κάθε φορά που βλέπει ένα ράφι με βιβλία, αναδιατάσσει τα βιβλία έτσι ώστε όλα τα μεγάλα βιβλία να εμφανίζονται στα αριστερά, ακολουθούμενα από όλα τα μεσαίου μεγέθους βιβλία, και στη συνέχεια όλα τα μικρά βιβλία να είναι στα δεξιά. Για να το κάνει αυτό επιλέγει επανειλημμένα δύο οποιαδήποτε βιβλία και ανταλλάσσει τις θέσεις τους. Αυτή η αλλαγή των θέσεων των δύο βιβλίων ονομάζεται ανταλλαγή (swap).

Βοηθήστε τη Βαλεντίνα να προσδιορίσει τον ελάχιστο αριθμό ανταλλαγών που απαιτούνται για να τακτοποιήσει ένα ράφι με βιβλία όπως το επιθυμεί.

Είσοδος

Η είσοδος θα αποτελείται από ακριβώς μία γραμμή που θα περιέχει τουλάχιστον έναν χαρακτήρα.

Ο ακόλουθος πίνακας δείχνει πώς κατανέμονται οι ~15~ διαθέσιμοι βαθμοί:

~7~ βαθμοί	το πολύ ~1000~ χαρακτήρες	κάθε χαρακτήρας θα είναι ~L~ ή ~S~
~2~ βαθμοί	το πολύ ~500000~ χαρακτήρες	κάθε χαρακτήρας θα είναι ~L~ ή ~S~
~4~ βαθμοί	το πολύ ~1000~ χαρακτήρες	κάθε χαρακτήρας θα είναι ~L~, ~M~, ή ~S~
~2~ βαθμοί	το πολύ ~500000~ χαρακτήρες	κάθε χαρακτήρας θα είναι ~L~, ~M~, ή ~S~

Έξοδος

Εξάγετε έναν ακέραιο αριθμό, τον ελάχιστο δυνατό αριθμό ανταλλαγών που απαιτούνται για να να ταξινομηθούν τα βιβλία ώστε όλες οι εμφανίσεις του ~L~ να είναι πρώτες, ακολουθούμενες από όλες τις εμφανίσεις του ~M~,και έπειτα όλες τις εμφανίσεις του ~S~.

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

input

LMMMS

output

0

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

Τα βιβλία είναι ήδη τακτοποιημένα κατά τις επιθυμίες της Βαλεντίνας.

input

LLSLM

output

2

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

Αντικαθιστώντας το ~S~ και το ~M~, καταλήγουμε στο ~LLMLS~. Στη συνέχεια, το ~M~ μπορεί να αντικατασταθεί με το ~L~ στα δεξιά του. Αυτός είναι ένας τρόπος που χρησιμοποιούμε δύο ανταλλαγές για να τακτοποιήσουμε τα βιβλία όπως τα θέλει η Βαλεντίνα. Δεν είναι δυνατόν να χρησιμοποιήσουμε λιγότερες ανταλλαγές, επειδή και το ~S~ και το ~M~ πρέπει να αλλάξουν θέση, αλλά αν χρησιμοποιούσαμε μία ανταλλαγή για να τα τοποθετήσουμε, δεν θα αφήναμε τα βιβλία τοποθετημένα όπως τα θέλει η Βαλεντίνα να είναι.