In this problem, let's call the alphabet string the string that consists of all uppercase English letters in the order they appear in the alphabet: "ABCDEFGHIJKLMNOPQRSTUVWXYZ". Given a string consisting of uppercase English letters, your task is to find the length of the shortest substring that contains the alphabet string as a subsequence.

Note

A substring is a contiguous sequence of characters within a string. For instance, "isipp" is a substring of "missisippi". For example, "Itwastimes" is a subsequence of "Itwasthebestoftimes" but not a substring.

A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements. For example, for the string "book", some example subsequences are "b", "ok", "oo", "bk", and "book". However, "obk" and "kb" are not subsequences of "book" because they don't preserve the original order.

Example

Let's assume that the input string is "FORCESABCDEFDIVGHIJKLMNOPQRSTUVWXYZ". The shortest substring that contains the alphabet string as a subsequence is "ABCDEFDIVGHIJKLMNOPQRSTUVWXYZ" (note the alphabet string in bold). Because its length is 29, the answer is 29.

Function description

Complete the solve function provided in the editor. This function takes the following 1 parameter and returns the length of the shortest substring that contains the alphabet string as a subsequence.

\(S\): Represents the String.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

The first and only line contains a string \(S\), consisting of uppercase English letters.

Output format

Print the length of the shortest substring that contains the alphabet string.

Code snippets

Code snippets are written in languages C, C++, Java, Python.

Constraints

\(26 ≤ length \space of \space S ≤ 10^5 \\S \space consists \space of \space uppercase \space English \space letters. \\It's \space guaranteed \space that \space there \space exists \space at \space least \space one \space such \space substring.\)