Cho một xâu \(S\) có \(N\) kí tự latinh thường \((a -> z)\).

Người ta kí hiệu \(S_i\) là kí tự thứ \(i\) khi đánh số xâu \(S\) từ \(1 -> N\) từ trái qua phải.

Một xâu được gọi là xâu dài dòng nếu như tồn tại ít nhất một kí tự trong xâu đó xuất hiện ít nhất hai lần.

Ví dụ: xâu acbc hay \(aabbbc\) là các xâu dài dòng.

Yêu cầu: Đếm số lượng bộ \((i,j)\) trong đó \(1 \leq i \leq j \leq N\) và xâu con \(S_i S_(i+1)… S_j\) là xâu dài dòng.

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương \(N (2 \leq N \leq 10^5)\) là độ dài của xâu S.
• Dòng thứ hai gồm \(N\) kí tự latinh in thường biểu diễn xâu \(S\).

Kết quả ra:

• Một dòng duy nhất là số lượng xâu dài dòng tìm được.

Examples

Giải thích

• ví dụ: 4 xâu con là xâu dài dòng: \(abca,cac,bcac,abcac\)

Ràng buộc:

• Subtask1: 30% số test tương ứng với tất cả ký tự trong xâu S đều giống nhau.
• Subtask2: 40% số test tiếp theo ứng với \(N \le 1000\).
• Subtask3: 30% số test còn lại không có ràng buộc gì.