今天是马特维的生日。他从来不知道要什么礼物,所以朋友们给了他一根长度为 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) 组获得的。