width = 3 buckets = [] needed = dict() while True: border = width * 4 - 4 inside = (width-2)**2 count = border + inside width += 2 if count > 20000: break buckets.append(count) needed[count] = (border, inside) input() line = input() class Count: def __init__(self): self.x = 0 self.y = 0 def sub(self, char): self.x -= char == 'X' self.y -= char == 'O' def add(self, char): self.x += char == 'X' self.y += char == 'O' counts = {b: Count() for b in buckets} seq = 0 for idx, char in enumerate(line): for bucket in buckets: counts[bucket].add(char) if idx >= bucket: sub = idx - bucket counts[bucket].sub(line[sub]) need = needed[bucket] count = counts[bucket] seq += (count.x, count.y) == need or (count.y, count.x) == need print(seq) # print(check(len(line) - 1))