Longest String Chain

You are given a list of words. A word X is a predecessor of word Y if and only if we can add exactly one letter anywhere in X without changing the order of the other characters to form Y. A word chain is a sequence of words where each word is a predecessor of the next one. Your task is to determine the length of the longest possible word chain.

Explanation: For example, if the input is a b ba bca bda bdca, the longest chain is "a" -> "ba" -> "bda" -> "bdca" with length 4.

Formula: Given a word w, let dp(w) be the length of the longest chain ending with w. Then, \[ dp(w) = 1 + \max_{w' \text{ is predecessor of } w} dp(w') \] If no predecessor exists, then dp(w)=1.

inputFormat

The first line contains an integer n denoting the number of words. The next line contains n words separated by spaces.

For example:

6
a b ba bca bda bdca

outputFormat

Output a single integer, the length of the longest chain.

6
a b ba bca bda bdca

4