CF451D.Count Good Substrings

We call a string good, if after merging all the consecutive equal characters, the resulting string is palindrome. For example, "aabba" is good, because after the merging step it will become "aba".

Given a string, you have to find two values:

1. the number of good substrings of even length;
2. the number of good substrings of odd length.

我们称一个字符串是“好的”，如果将其所有连续的相同字符合并后，所得字符串为回文串。例如，"aabba" 是好的，因为合并后变为 "aba"。

给定一个字符串，你需要求出以下两个值：

1. 长度为偶数的“好”子串的数量；
2. 长度为奇数的“好”子串的数量。

The first line of the input contains a single string of length n (1 ≤ n ≤ 105). Each character of the string will be either 'a' or 'b'.

输入的第一行包含一个长度为 $n$（$1 ≤ n ≤ 10^5$）的字符串。该字符串的每个字符均为 'a' 或 'b'。

Print two space-separated integers: the number of good substrings of even length and the number of good substrings of odd length.

输出两个用空格分隔的整数：偶数长度的好子串的数量和奇数长度的好子串的数量。

In example 1, there are three good substrings ("b", "b", and "bb"). One of them has even length and two of them have odd length.

In example 2, there are six good substrings (i.e. "b", "a", "a", "b", "aa", "baab"). Two of them have even length and four of them have odd length.

In example 3, there are seven good substrings (i.e. "b", "a", "b", "b", "bb", "bab", "babb"). Two of them have even length and five of them have odd length.

Definitions

A substring s[l, r] (1 ≤ l ≤ r ≤ n) of string s = _s_1_s_2... s__n is string s__l__s__l + 1... s__r.

A string s = _s_1_s_2... s__n is a palindrome if it is equal to string s__n__s__n - 1... _s_1.

在示例 1 中，存在三个“好”子串（即 "b"、"b" 和 "bb"）。其中有一个长度为偶数，两个长度为奇数。

在示例 2 中，存在六个“好”子串（即 "b"、"a"、"a"、"b"、"aa"、"baab"）。其中两个长度为偶数，四个长度为奇数。

在示例 3 中，存在七个“好”子串（即 "b"、"a"、"b"、"b"、"bb"、"bab"、"babb"）。其中两个长度为偶数，五个长度为奇数。

定义

字符串 $s = s_1s_2\ldots s_n$ 的一个子串 $s[l,\,r]$（其中 $1 \leq l \leq r \leq n$）是指字符串 $s_l s_{l+1} \ldots s_r$。

字符串 $s = s_1 s_2 \ldots s_n$ 是回文串，当且仅当它等于字符串 $s_n s_{n-1} \ldots s_1$。