闪闪发光心动不已！
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

户山香澄非常喜欢kirakiradokidoki，她认为形如kirakirakira...kiradokidokidoki...doki（前面有至少1个kira，后面有至少1个doki）的序列是令人心动不已的！

现在，香澄会给你一个字符串s，我们定义该字符串的心动值为其所有“令人心动不已”的子序列的长度的最大值；特别的，如果不存在这样的子序列，则这个字符串的心动值为0。

请你输出这个字符串的心动值！

此处应该有一个子序列的定义：对于字符串s，我们将它的某些字符取出来，然后按照相对顺序排在一起组成的序列称为该字符串的子序列，如a,b,c,ab,ac,bc,abc都是abc的子序列，但d,abd,cba都不是abc的子序列。

输入描述:

第一行有一个正整数n（1 \leq n \leq 10^5）表示字符串s的长度

第二行一个长度为n，由小写英文字母组成的字符串s。

输出描述:

输出一个非负整数x，表示字符串s的心动值。
示例1

输入

复制 
25
kirakirakirapdokikirakira

输出

复制 
16

说明

该字符串的一个长度为16的“令人心动不已”的子序列为kirakirakiradoki，注意kirakirakirakirakira是不合法的（没有出现doki）