题目描述

临海听潮意，入林闻籁鸣。这是一座依山傍水、宁静祥和的小镇，在这里人们很少担心自己家里的物品故障损坏，因为 Kanan 总能帮大家修好。Kanan 是这片地区首屈一指的机械师；虽然她还年轻，但是娴熟的技艺加上慷慨的性格使得她平时总会收到人们的修理委托，据说就连那位遗世独立的魔王遇到了问题都得求助她。在帮人修理时， Kanan 会接触到千奇百怪的使用说明书。其中一些说明书有着不可思议的折叠结构，Kanan 为了理解机械的构造会在修理之前展开说明书，可在修好之后按照原来的折痕折回原状却比修理本身更费劲。

对于所有折痕互相平行的说明书，可以按照说明书上文字的阅读顺序从上到下给每条折痕分别编号 $1, 2, \cdots, N$，这 $N$ 条折痕将说明书分成了 $(N+1)$ 条纸带。每条折痕可能为两种形态之一：一种是垂直纸面向内凸出，对应将纸的上下两半向前对折；一种是垂直纸面向外凸出，对应将上下两半向后对折。根据折痕截面的形状，分别使用小写字母 v 表示向内凸出的折痕，^ （ASCII 码为 $94$）表示向外凸出的折痕。假设所有纸带的宽度都是一样的，并且折纸的过程中说明书不发生形变，那么沿着一条折痕对折后两侧的纸能够重合，当且仅当两侧的折痕是相反的；即，如果沿着第 $k$ 条折痕折叠，那么对于所有满足 $1\le k-m<k+m\le N$ 的正整数 $m$，第 $(k-m)$ 条折痕和第 $(k+m)$ 条折痕的形态是相反的。例如，对于折痕依次为 v^v^^^^v 的说明书，可以沿其第 $7$ 条折痕进行折叠。根据定义可知，一张说明书总能沿着第一条或最后一条折痕进行折叠。折叠之后的说明书可以用被折叠的折痕两侧中，剩余折痕数量较多一侧的折痕表示，如 v^v^^^^v 沿着第 $7$ 条折痕折叠后得到 v^v^^^。如果被折叠的折痕两侧折痕数量相等，那么用哪一侧的折痕表示折叠后的纸都可以，因为折痕在三维空间中是旋转对称的。特别地，对只剩下一条折痕的说明书，即 v 或 ^ 进行折叠后，所有 $(N+1)$ 条纸带都重叠在一起，此时称这张说明书被折叠整齐。

虽然按顺序依次折叠每一条折痕，总能将说明书折叠整齐，但 Kanan 觉得这样并不美观。一种美观的折法应该尽量少折，并且每次折的时候折痕两侧应该尽可能的对称。定义一种折法的不对称程度为每次折叠时，被折叠的折痕两侧的折痕数量之差的总和。给出一张说明书的折痕，Kanan 想知道最少需要折多少次才能将这张说明书折叠整齐，以及所有折叠次数最少的折法中，不对称程度的最小值。

输入格式

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

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

输出格式

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

3
^vv

2 0

8
v^v^^^^v

6 15

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

14 201

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

24 663

提示

样例 #1 解释

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

子任务

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

题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2024 初赛 官方仓库（https://github.com/ckw20/thupc2024_pre_public）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。