Cho một xâu \(S\) gồm các chữ cái Latin in hoa, bài toán đặt ra: Bạn được phép xóa đi một vài kí tự để thu được xâu không giảm. Xâu \(X(x_1x_2…x_n)\) được gọi là xâu không giảm nếu mọi cặp \(i < j, x_i ≤ x_j\) (\(x_i\) đứng trước hoặc bằng \(x_j\) trong thứ tự từ điển).

Yêu cầu: Hãy viết chương trình tìm độ dài của xâu không giảm dài nhất.

Dữ liệu vào: Từ tệp văn bản BAI3.INP, có cấu trúc: Một dòng duy nhất chứa xâu \(S\).

Dữ liệu ra: Đưa ra tệp văn bản BAI3.OUT gồm một số nguyên duy nhất là độ dài của xâu không giảm dài nhất.

Ví dụ:

Input

DABC

Output

3

Ràng buộc:

• Có 15% test tương ứng 15% số điểm với kí tự tăng dần theo vị trí xuất hiện và độ dài của xâu không quá \(20\);
• Có 35% test tương ứng 35% số điểm với độ dài của xâu không quá \(20;\)
• Có 35% test tương ứng 35% số điểm với độ dài của xâu không quá \(1000;\)
• (MR) Có 15% test khác ứng với 15% số điểm còn lại của bài với độ dài của xâu không quá \(2*10^5\).