题目描述

临海听潮意，入林闻籁鸣。这是一座依山傍水、宁静祥和的小镇，在这里人们很少担心自己家里的物品故障损坏，因为 Kanan 总能帮大家修好。Kanan 是这片地区首屈一指的机械师；虽然她还年轻，但是娴熟的技艺加上慷慨的性格使得她平时总会收到人们的修理委托，据说就连那位遗世独立的魔王遇到了问题都得求助她。在帮人修理时，Kanan 会接触到千奇百怪的折叠结构说明书。

对于所有折痕互相平行的说明书，可以按照说明书上文字的阅读顺序从上到下给每条折痕分别编号 $1, 2, \cdots, N$，这 $N$ 条折痕将说明书分成了 $(N+1)$ 条纸带。每条折痕可能为两种形态之一：

• 垂直纸面向内凸出，对应将纸的上下两半向前对折，用字母 v 表示
• 垂直纸面向外凸出，对应将上下两半向后对折，用字母 ^（ASCII 码为 94）表示

假设所有纸带的宽度都一样，且折纸过程中说明书不发生形变，那么沿着一条折痕对折后两侧的纸能够重合，当且仅当对于所有满足 $1 \le k-m < k+m \le N$ 的正整数 $m$，第 $(k-m)$ 条折痕和第 $(k+m)$ 条折痕的形态是相反的。

例如，对于折痕依次为 v^v^^^^v 的说明书，可以沿其第 $7$ 条折痕进行折叠。根据定义可知，一张说明书总能沿着第一条或最后一条折痕进行折叠。

折叠之后的说明书可以用被折叠的折痕两侧中，剩余折痕数量较多一侧的折痕表示。如果两侧折痕数量相等，那么用哪一侧的折痕表示都可以。特别地，对只剩下一条折痕的说明书（即 v 或 ^）进行折叠后，所有纸带都重叠在一起，此时称这张说明书被折叠整齐。

虽然按顺序依次折叠每一条折痕，总能将说明书折叠整齐，但 Kanan 觉得这样并不美观。一种美观的折法应该尽量少折，并且每次折的时候折痕两侧应该尽可能的对称。

定义一种折法的不对称程度为每次折叠时，被折叠的折痕两侧的折痕数量之差的总和。

给出一张说明书的折痕，Kanan 想知道：

1. 最少需要折多少次才能将这张说明书折叠整齐
2. 所有折叠次数最少的折法中，不对称程度的最小值

---

输入格式

第一行包含一个正整数 $N$，表示折痕的条数。保证 $1 \le N \le 5000$。

第二行包含一个字符串 $s$，按顺序表示每条折痕。保证 $|s| = N$，且 $s$ 仅由 v 和 ^ 组成。

---

输出格式

输出一行两个非负整数，分别表示最少的折叠次数和最小化折叠次数的前提下的最小不对称程度，两个数之间用一个空格隔开。

---

样例 1

输入：

3
^vv

输出：

2 0

解释：如果先沿着中间的折痕对折，那么两侧的纸恰好重合，此时再对折一次即可将说明书折叠整齐。

---

样例 2

输入：

8
v^v^^^^v

输出：

6 15

---

样例 3

输入：

40
v^vv^v^^v^^vvvv^v^^v^^^vv^^vvvv^v^^v^^^v

输出：

14 201

---

样例 4

输入：

56
v^vvvvvvv^v^^vv^v^^v^^^^v^^v^vvvv^^vvvv^v^^v^^^vv^^vv^v^

输出：

24 663

---

数据范围

对于所有数据，保证 $1 \le N \le 5000$，$|s| = N$ 且 $s$ 仅由 v 和 ^ 组成。