Holiday Season
Tag(s):

## Searching

Problem
Editorial
Analytics

It's a holiday season for all school students around the world! Unfortunately, Mahamba is busy preparing for International Olympiad in Informatics, which will be held in Tehran, Iran. He is now facing a new challenge from his teacher Aceka, and it goes something like this:

You have a string x of length N, which consists of small English letters. You have to find the number of indexes a, b, c and d, such that $1 <= a < b < c < d <= N$ and $x_a == x_c$, as well as $x_b == x_d$.

He is baffled and definitely needs some help. So, you, the best programmer in Lalalandia, decided to give him a hand!

Input format

The first line contains the number N - the length of a string x. The second line contains the string x itself.

Output format

The first and only line should contain the answer to the problem.

Constraints

$1 <= N <= 2000$

The string x only contains small English letters.

SAMPLE INPUT
5
ababa
SAMPLE OUTPUT
2
Explanation

There are only 2 variants: (a=1,b=2,c=3,d=4) and (a=2,b=3,c=4,d=5)

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

IndiaHacks 2017: Programming Wave 1.0 [Eliminator]

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Math > Basic Math
• Algorithms > Dynamic Programming