Little Elephant from the Zoo of Lviv likes strings that consist of characters 'R', 'G' and 'B'. You are given a String list. Concatenate all elements of list to get the string S of length N. The characters in S are numbered from 0 to N-1, inclusive.
You are also given int minGreen. Little Elephant thinks that string is nice if and only if it contains a substring of at least minGreen consecutive characters 'G'. For example, if minGreen = 2, then strings "GG", "GGRGBB" and "RRRGRBGGG" are nice, but "G", "GRG", "BBRRGRGB" are not.
Little Elephant wants to know the number of quadruples of integers (a,b,c,d) such that:
Compute and return the number of such quadruples (a,b,c,d).
- Each of a, b, c, d is between 0 and N-1, inclusive.
- a <= b and c <= d. (Both a..b and c..d are valid ranges of values.)
- b < c. (The entire range a..b lies before the range c..d.)
- The string T = S[a..b] + S[c..d] is nice.