alphabrackets

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

Submitting to 'alphabrackets'


You're not logged in! Click here to login


Submitting to 'alphabrackets'


You're not logged in! Click here to login


Submitting .cpp to 'alphabrackets'


You're not logged in! Click here to login

Time Limit: 0.5 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: Dec Course Final Contest 2017

Subtask Score
1 16
2 18
3 14
4 23
5 13
6 16
7 0