Xâu đơn là xâu gồm ~1~ chữ cái, với độ dài bằng vị trí của chữ cái đó trong bảng chữ cái. Ví dụ:

• a, bb, dddd là những xâu đơn hợp lệ.

• ab, aa, bbbb không phải là xâu đơn.

Xâu ghép là xâu gồm nhiều xâu đơn được ghép lại với nhau, và xâu đơn trước phải có chữ cái bé hơn chữ cái của xâu đơn ở sau, ví dụ:

• a, abb, adddd là những xâu ghép hợp lệ.

• bba, aabb, bbbb không phải là xâu ghép.

Cho xâu ~s~ gồm các chữ cái viết thường, tìm xâu con dài nhất (không nhất thiết phải liên tiếp) trong ~s~ là một xâu ghép. In ra độ dài của xâu đó.

Input

Một dòng duy nhất là xâu ~s~ ~(|s| \leq 10^5)~.

Output

In ra độ dài xâu con dài nhất thõa mãn đề bài.

Scoring

Sample Input 1

adddebbaacccd

Sample Output 1

6

Sample Input 2

abbcdccddd

Sample Output 2

7

Notes

Ở ví dụ ~1~: Xâu ghép dài nhất trong test ví dụ là abbccc.

Ở ví dụ ~2~: Xâu ghép dài nhất trong test ví dụ là abbdddd.