Đoạn ngoặc hợp lệ dài nhất

Bối cảnh và bài toán

Một bộ phân tích nhận chuỗi chỉ gồm ( và ). Cần tìm những đoạn liên tiếp tạo thành chuỗi ngoặc đúng. Hệ thống quan tâm tới độ dài lớn nhất và số đoạn có đúng độ dài lớn nhất đó.

Yêu cầu

In độ dài lớn nhất của một substring ngoặc hợp lệ và số substring đạt độ dài đó. Nếu không có substring hợp lệ không rỗng, in 0 1.

Input

• Một dòng chứa chuỗi s.

Output

In hai số L C.

Ràng buộc

• 1 <= |s| <= 10^6
• s[i] là(hoặc)``

Chấm điểm

Ví dụ 1

Input

)((())))(()())

Output

6 2

Giải thích. Có hai đoạn hợp lệ dài 6: ((())) và (()()).

Ví dụ 2

Input

))(

Output

0 1

Giải thích. Không có cặp ngoặc hợp lệ; theo quy ước in 0 1.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces 5C – Longest Regular Bracket Sequence.

Tham khảo: https://codeforces.com/problemset/problem/5/C