Maximum Likelihood Fitting of a Dog's Bark Sequence

In a parallel world, Xiao Wei, the ML expert from Z University, is fascinated by a barking dog whose barks vary in pitch and rhythm. He models the dog's bark sequence using two symbols: H for a high-pitched bark and L for a low-pitched bark. For modeling simplicity, every observed bark sequence always starts with two H sounds. Moreover, due to the dog’s limited attention span, it is assumed that the i-th bark depends only on the two immediately preceding barks (i.e. the (i-1)-th and (i-2)-th barks).

The model is represented by a mapping \( \theta \) of the form:

[ \theta : [L, H]^2 \times [L, H, \gamma] \to \mathbb{P}, ]

where \( \gamma \) denotes the termination symbol of the bark sequence. For example, \( \theta(L, H; L) = 0.6 \) means that given the two preceding barks are L and H, the probability of the next bark being L is 0.6. The observed bark sequence \( s_{[1:m]} \) (of length \( m \)) is modeled by the likelihood:

[ \prod_{i=3}^{m+1} \theta(s_{i-2}, s_{i-1}; s_{i}), ]

where we define \( s_{m+1} = \gamma \) (the termination symbol). Since the product can be extremely small, you are only required to output its natural logarithm, i.e.,

[ \ln \left( \max \prod_{i=3}^{m+1} \theta(s_{i-2}, s_{i-1}; s_{i}) \right). ]

</p>

Given that you have only one bark sequence as data, the maximum likelihood estimation for each context \( (a,b) \) (with \( a,b \in \{H,L\} \)) is achieved by setting for each possible outcome \( x \in \{H,L,\gamma\} \):

[ \theta(a,b;x) = \frac{n(a,b;x)}{\sum_{y \in {H,L,\gamma}} n(a,b;y)}, ]

where \( n(a,b;x) \) is the number of times the outcome \( x \) follows the context \( (a,b) \) in the augmented sequence (including the termination transition). Under this choice, the maximum likelihood value is

[ \prod_{(a,b)} \prod_{x \in {H,L,\gamma}} \left(\frac{n(a,b;x)}{\sum_{y} n(a,b;y)}\right)^{n(a,b;x)}, ]

and you are to output its natural logarithm.

inputFormat

The input consists of two lines:

1. An integer \( m \) (\( m \ge 3 \)) representing the length of the observed bark sequence.
2. A string of length \( m \) consisting of characters H and L. It is guaranteed that the first two characters will be H (i.e. the sequence always starts with "HH").

outputFormat

Output a single line containing the natural logarithm of the maximum likelihood value computed as described.

sample

3
HHH

-1.3862943611198906

</p>