小明拿到了一个字符串s，仅由小写字母组成。现在他想知道这个字符串中有多少对(i,j),1 =<i<= j=<n 满足 s中第i到j个字符组成的子串是好字符串。

定义字符串t是好字符串，当且仅当t满足以下条件

1、t 的长度是奇数

2、t 中每个字母的出现次数不超过 3

3、t中任意两个相邻字母都不相同

注:子串是指字符串中取出一段连续的部分得到的字符串

输入格式

输入一个非空字符串 s，仅由小写字母组成。

输出格式

输出一个整数，表示s中有多少个子串是好字符串

样例

abcdbca

16

数据范围

s 长度是=< 1000 的正整数

小明有 n袋糖果，排成一个圈，其中顺时针数第i袋糖果有非负整数 a; 个，3 ≤n≤10000,0 ≤a_i ≤10000。第i袋糖果和第i+1袋糖果位置相邻(1 ≤i<n)，第n 袋和第 1袋相邻。

之后，小明把每个比相邻两个位置糖果数量都更多的袋子画上了记号

然后，小明把每个画了记号的袋子的糖果取出一半(向下取整)吃掉，把袋子里剩余的糖果都倒进桶里。

最后，小明会把桶里的糖果平均地放回 n个袋子，多余的无法平分的部分也吃掉。

请你算出小明总共吃了多少个糖果，以及结束之后糖果最多的一袋有多少个糖果。

输入格式

输入第一行一个正整数 n 表示袋子数。

输入第二行几 个由空格隔开的正整数 a₁,a₂,...,a_n 依次表示每一袋糖果一开始的数量,

输出格式

输出一行两个整数，用空格隔开，依次表示小明总共吃的糖果数量和结束之后糖果最多的一袋的数量

样例

4

2 5 4 7

8 5

样例 1解释

有4袋，一开始糖果数是 2,5,4,7。被标记的袋子是第 2,4袋。

第2袋有5个，吃掉 2个，放桶里3个。

第4袋有 7个，吃掉3个，放桶里 4个。

桶里一共3+4=7个，放回每个袋子1个，多余3个吃掉。

总共吃掉2+3+3=8个，且最后每个袋子数量依次是3,1,5,1，最多的是5个。

数据范围

3 ≤n≤10000,0 ≤a_i≤ 10000