Patio

Interview

Time limit3sMemory limit1024 MB

Summary

Count contiguous substrings of a tile string that form a square patio with a one-tile border of one color and an interior of the other.

Level: Medium5 of 10
Topics: String, Prefix sum, Implementation
Solved: No attempts yet

Problem

Cimrman wants to make a square patio floor using tiles of two colors, red and blue. The patio floor should look like this (with the colors slightly faded in time):

Figure 1: One of Cimrman's perfect patios

More specifically, the patio must have a square shape. Tiles of one of the colors are used as the border of the square. The border must be exactly one tile thick. The tiles of the other color are used to fill the rest of the square. The side of the square must consist of at least 3 tiles.

Cimrman has a long file of square red tiles and blue tiles. All tiles are the same size. From this file, Cimrman takes some tiles for the floor. Manipulating the file is clumsy, so the taken tiles must form one contiguous subsequence of the file.

Before Cimrman starts the construction, he needs to know how many suitable contiguous subsequences of tiles are in the file.

Input

The input consists of two lines. The first line contains an integer $N$ ( $1 \le N \le 2 \times 10^5$ ), the length of the file of tiles. The second line contains a string of $N$ characters representing the file of tiles. Only two characters appear in the string. "X" represents a blue tile and "O" represents a red tile.

Output

Output the number of contiguous subsequences in the file from which Cimrman can construct a nice square patio floor.

Examples2

Example 1
Input
```
9
XXXOXXXXX
```
Expected output
```
1
```
Example 2
Input
```
10
XOXXXXXXXX
```
Expected output
```
2
```