Có n bạn nam và nữ đứng thành một vòng tròn, mỗi bạn được gán một số hiệu từ 1 tới n theo chiều kim đồng hồ bắt đầu từ một bạn nào đó. Người ta muốn chọn một số bạn đứng liên tiếp trên vòng tròn sao cho số bạn được chọn lớn hơn 0, đồng thời số bạn nam đúng bằng số bạn nữ.
Hãy cho biết số cách chọn thỏa mãn điều kiện trên (Hai cách chọn được xem là khác nhau nếu tồn tại ít nhất một bạn được chọn trong một cách nhưng không được chọn trong cách còn lại).
Input
Dòng thứ nhất chứa một số nguyên dương n <= 10^6.
Dòng thứ 2 chứa n ký tự liên tiếp nhau. Ký tự thứ i là dấu ‘+’ nếu bạn thứ i là bạn nam, là dấu ‘-’ nếu đó là bạn nữ (1 <= i <= n).
Output
Ghi ra 1 số duy nhất là số cách chọn tìm được.
Ví dụ
Input
5
- + + - +
Output
7
Giải thích
Bài này mình chỉ làm được với O(n^2), ai biết giúp mình làm trong O(n) thì giúp mình với. Mình cảm ơn!
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?