← 返回题目列表

Codeforces · 718/E

E. 玛特维的生日

中文机器翻译题面 查看原题

今天是马特维的生日。他从来不知道要什么礼物,所以朋友们给了他一根长度为 n 的绳子 s。该字符串仅包含前八个英文字母:“a”、“b”、...、“h”。

我想到的第一个问题是:谁可能需要一些绳子?马特维是一个特别的男孩,所以他立即找到了如何处理这根绳子。他用它构建了一个无向图,其中顶点对应于字符串中的位置,并且如果至少满足以下条件之一,则不同位置 a 和 b (1 ≤ a, b ≤ n) 之间存在一条边:

1. a 和 b 相邻,即 |a - b| = 1。
2.位置a和b包含相同的字符,即sa = sb。

然后 Matvey 决定找到该图的直径。直径是所有顶点对之间的最大距离(最短路径的长度)。此外,Matvey 想要找到使它们之间的距离等于图的直径的顶点对的数量。由于他是一位非常酷且经验丰富的程序员,他很快就解决了这个问题。你也会这样做吗?

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 100 000) - 字符串的长度。

第二行包含字符串 s 本身。保证 s 仅包含英文字母的前八个字母。

输出

打印两个整数 - 图形的直径和距离等于直径的位置对的数量。

示例

输入 #1

3
abc

输出 #1

2 1

输入 #2

7
aaabaaa

输出 #2

2 4

注意

考虑第二个示例。

最大距离为 2。它是针对 (1, 4)、(2, 4)、(4, 6) 和 (4, 7) 组获得的。