3s，1024MB。时间建议适当调至 std.cpp 的三倍左右。

题目背景

$\textcolor{black}h\textcolor{red}{\text{vAC}}$ 又收到了好多情书。不过他并没有在意。某一天他将所有情书抖在了一起，为了打发无聊的假期时光，研究起了这些情书的 LIS 问题。于是便有了这道题。

题目描述

$\textcolor{black}h\textcolor{red}{\text{vAC}}$ 最近对最长上升子序列（Longest Increasing Subsequence — LIS）很感兴趣，所以他尝试对字符串做 LIS：

他会把这个串划分为若干段形成一个字符串序列，然后求出这些子串们 LIS 的长度。

一些有用的例子：

对于数串 $\{\textcolor{red}1, \textcolor{red}2, 5,\textcolor{red}4,2,3\}$ 有最长上升子序列 $\{1, 2, 4\}$ 或 $\{1, 2, 3\}$。无论如何长度为 $3$。

可以注意到此时定义上升为字典序大于，即对于字符串 $b$ 对 $a$ 是上升的，可以定义为：存在一个下标 $i \le \min\{|a|, |b|\}$​ 在字符串中满足：

$$\forall j< i,a_j = b_j\ \text{and}\ a_i < b_i$$

请注意，变态出题人为了加强题目难度，因此拓宽了字符域，为 0~9、a~z、A~Z、以及标点符号四个 ,.!?。比较大小的方式可以直接参照 ASCII 即 C++ 中默认 char 类型比较大小方式。

例如串 $\{\text{ababab}\}$ 可以划分成字符串序列 $\{\textcolor{red}{\text{a}}\text{|bab|}\textcolor{red}{\text{ab}}\}$，此时这个序列的 LIS 的长度是 $2$。

但是如果将该串划分为 $\{\text{\textcolor{red}a|b|\textcolor{red}{ab}|\textcolor{red}b}\}$ LIS 的长度是 $3$。

现在有一个长度为 $n$ 的字符串 $s$。

$\textcolor{black}h\textcolor{red}{\text{vAC}}$ 希望他划分 $s$ 得到的字符串序列的 LIS 长度尽可能大。

他想知道在所有可能的划分方式中，LIS 长度的最大值是多少？

输入格式

第一行输入一个数 $n$ 表示字符串的长度。

第二行一行长度为 $n$ 的字符串。

保证 $s$​​​ 仅有 0~9、a~z、A~Z、以及标点符号四个 ,.!?。

输出格式

输出一行，一个数，表示字符串 $s$ 中所有可能的划分方式中 LIS 长度的最大值。

6
ababab

3

6
aaabbb

4

17
kewudewinnerhvAC!

7

提示

请注意与众不同的时空范围。此题略微卡常，但 std.cpp 的三倍左右理应通过。

数据范围：

对于 $10\%$ 的数据满足 $n \le 15$；

对于另外 $16\%$ 的数据满足 $n\le 100$；

对于另外 $20\%$ 的数据满足 $n\le 300$；

对于另外 $24\%$ 的数据满足 $n\le 1000$；

对于 $100\%$ 的数据满足 $1\le n\le 2\times 10^4$。

特别的，在所有数据中均匀散布着 $48\%$ 的数据满足只有 01234abcdeABCDE,.!? 这些字符构成字符串。