A - 字符串

题目背景

Legends never die

When the world is calling you

Can you hear them screaming out your name?

Legends never die

They become a part of you

Every time you bleed for reaching greatness

Legends never die

题目描述

给定长度为 $n$ 的字符串 $s$ 。你现在要进行恰好一次操作：

选择 $1\le l\le r\le n$ ，把 $s$ 的子串 $s[l:r]$ 删去，得到新的串 $t$ 。

你想知道：所有可能的操作最后得到的不同的 $t$ 个数。

输入格式

第一行输入一个整数 $n$ ，代表字符串的长度。

第二行输入一个长度为 $n$ 的字符串 $s$ 。

输出格式

输出一行一个整数，表示此时的答案。

样例

样例输入

5
abbab

样例输出

11

数据范围

对于所有数据，$1\le n\le 10^6$ ，每个字符都是小写字母。

子任务 1 ( 20% ) : $1\le n\le 100$ 。

子任务 2 ( 20% ) : $1\le n\le 500$ 。

子任务 3 ( 20% ) ：$1\le n\le 4000$ 。

子任务 4 ( 40% ) : 无特殊限制。