Problem Description
An valid alphabracket string consists of a series of upper and lowercase letters, and must be in the form of:
- an empty string,
- A#a where A represents an uppercase letter, a represents a lowercase version of the same letter, and # represents a valid alphabracket string, or
- #@, where # and @ are two valid alphabracket strings.
For example, BAaCcb is a valid alphabracket string while ABab is not.
Given a string S consisting of only uppercase and lowercase letters, determine how many non-empty substrings of S are valid alphabracket strings.
Input
The first and only line of input will contain one string, S.
Output
The output should contain one integer, the number of non-empty substrings of S which are valid alphabracket strings.
Limits
Subtask 1 (16%): 1 ≤ length of string ≤ 300.
Subtask 2 (18%): 1 ≤ length of string ≤ 2000.
Subtask 3 (14%): 1 ≤ length of string ≤ 100000, the string will only consist of 'A' and 'a', and all 'A's will come before any 'a'.
Subtask 4 (23%): 1 ≤ length of string ≤ 100000, the string will only consist of 'A' and 'a'.
Subtask 5 (13%): 1 ≤ length of string ≤ 100000.
Subtask 6 (16%): 1 ≤ length of string ≤ 2000000.
Subtask 7 (0%): Sample Testcases.
Sample Input 1
BAaCcb
Sample Output 1
4
Sample Input 2
ABab
Sample Output 2
0
Sample Input 3
aAaAa
Sample Output 3
3