В гостях у Марічки

Обмеження: 1 сек., 256 МіБ

Марічка запросила Зеника до себе додому, щоб погодувати його, бо переживає за його канапковий раціон. Вона приготувала йому декілька страв і дозволила йому вибрати порядок в якому він буде їх їсти. Для цього вона дала йому рядок $s$, що містить перші букви приготованих страв. Наприклад, зі стравами spaghetti і borsch рядок $s$ буде рівний sb. Отже, аби вибрати порядок страв, йому необхідно переставити букви в цьому рядку.

Але в Зеника одні канапки на думці, тому він вирішив переставити букви у такий спосіб, аби отримати якнайбільшу кількість підрядків kanapka. Його цікавить їх максимальна можлива кількість, знайдіть це число.

Вхідні дані

У першому рядку задано одне ціле число $n$ — кількість страв, приготованих Марічкою.

У другому рядку задано рядок $s$ довжиною $n$ — перші букви приготованих страв.

Вихідні дані

У єдиному рядку виведіть відповідь — максимальну кількість підрядків kanapka, яку можна отримати переставивши символи заданого рядка.

Обмеження

$1 \le n \le 10^5$,

s складається виключно з малих літер англійського алфавіту,

5 балів — блок тестів в якому $n \le 10$,

10 балів — блок тестів в яких рядки містять лише букви k, a, n, p,

10 балів — блок тестів в якому $n \le 10^5$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
10 akcnxapazk	1

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
15 pkakvkcaapanank	2

Примітки

У другому прикладі переставивши букви можна отримати рядок vkkanapkanapkac.

Підрядки kanapka:

vk kanapka napkac,

vkkanap kanapka c.