Longest Alphabetically Ordered Substring

Given a string \( S \), find the longest substring in which the characters occur in a strictly increasing alphabetical order. Formally, a substring \( T \) of \( S \) is valid if for every \( i \) (\( 1 \leq i < |T| \)), \( T_i < T_{i+1} \). If there are multiple substrings with the same maximum length, return the one that appears first in \( S \).

Example: For \( S = \texttt{abacabadabacaba} \), the longest valid substring is \( \texttt{ab} \).

The input string may contain up to \( 10^5 \) characters.

inputFormat

The input consists of a single line containing the string \( S \).

outputFormat

Output the longest substring of \( S \) in which the characters are in strictly increasing alphabetical order. If multiple such substrings exist with the maximum length, output the first one found.

abacabadabacaba

ab