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

Обмеження: 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.