407238: GYM102700 H Happy game

Teresa and Fabio are wandering in the UNAL campus waiting for Nick to get out of classes for lunch. They are getting bored, Teresa came up with a game.

They will play on the only street of the campus, the street is a straight line divided by labeled cells. The game consists of many rounds. In each round, both of them will select 2 different cells from the street. They will stand at each chosen cell watching to each other, then they will start walking to each other $$$1$$$ step at a time until they meet at some point, either inside a cell or at the border of a cell.

A round is called happy if at each step the label of both cells where they are standing is the same, and they meet inside a cell, not at the border.

Nick could go out of class at any moment, so to maximize their fun, they are not gonna do rounds that are not happy. Also, they don't want to repeat any round, two rounds are considered equal if the labels while walking are the same in both rounds for Teresa and Fabio. For example, if the labels on the street are ababa a round with Fabio selecting cell 1 and Teresa selecting cell 3 is equal to a round with Fabio selecting cell 5 and Teresa selecting cell 3.

Can you determine the maximum number of happy rounds they would do?

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — The number of cells on the street.

Following line will contains $$$n$$$ lowercase english letters, which correspond to the labels of the street in order (from cell $$$1$$$ to cell $$$n$$$).

Print one integer that represents the maximum number of rounds the game could last.

1
c

0

3
aba

1

5
ababa

3

2
bb

0