BSSPC 2019 P7 - Learning The Alphabet

Problem Statement

p1geon is learning the alphabet in English class but he’s having difficulty memorizing the correct order.

Please help him find the longest subsequence of the letters he has written down which is in the correct order (that is there can be missing letters which can be filled in to create a correct subsequence of the alphabet).

Constraints

Subtask 1[10%]

$1 \le n \le 10$

Subtask 2[30%]

$1 \le n \le 10^3$

Subtask 3[60%]

$1 \le n \le 10^6$

Input Specification

The first line of input will be an integer, $n$, representing the length of the string.

The second line of input will be a string of letters of length $n$. The letters may be lowercase or uppercase but only the alphabetical order matters.

Output Specification

Output the length of the longest subsequence in the correct order.

Sample Input

8
AbCDabEz

Sample Output

6

Explanation

The longest subsequence of correct order is AbCDEz.