Maximize Properly Nested Gene Markers in Circular DNA

You are given a circular DNA sequence that has been transformed into a sequence of gene markers. For each gene type i, there is a unique start marker \(\texttt{s_i}\) and a unique end marker \(\texttt{e_i}\). The circular sequence is obtained by removing all the genetic material between markers so that only the markers remain.

In order to study whether markers of a gene type form a properly nested structure, one first cuts the circular DNA at an arbitrary position to form a linear sequence. Then, for each gene type, you extract the subsequence of markers (all occurrences of \(\texttt{s_i}\) and \(\texttt{e_i}\) in order). A gene type \(i\) is said to be properly nested if its marker subsequence forms a valid nested structure according to the following rules (and only these):

• \(\texttt{s_i e_i}\) is a properly nested structure.
• \(\texttt{s_i N e_i}\) is properly nested if \(N\) is a properly nested structure.
• If \(A\) and \(B\) are properly nested structures then their concatenation \(AB\) is also properly nested.

Note that the empty sequence is not considered properly nested. Effectively, if you treat \(\texttt{s_i}\) as an opening parenthesis and \(\texttt{e_i}\) as a closing parenthesis, then the subsequence must form a balanced parentheses string (with no extra markers) to be considered properly nested.

Your task is to choose a cutting location (an index in the circular sequence) so that when the sequence is read from that point (wrapping around at the end), the number of gene types whose extracted marker subsequence is properly nested is maximized. If multiple cut locations yield the same maximum number, report the smallest index (0-indexed).

inputFormat

The input consists of:

1. An integer \(n\) representing the number of markers in the circular DNA.
2. A line containing \(n\) markers separated by spaces. These are the markers in the circular order.
3. An integer \(k\) representing the number of gene types.
4. \(k\) lines follow, each containing two strings: the start marker and the end marker for the corresponding gene type.

The cutting location is defined as an index (0-indexed) in the sequence; if you cut at index \(i\), the linear sequence becomes \(w = \text{markers}[i], \text{markers}[i+1], \dots, \text{markers}[n-1], \text{markers}[0], \dots, \text{markers}[i-1]\).

outputFormat

Output two integers separated by a space: the maximum number of gene types that form a properly nested structure for some cutting, and the smallest cutting index that achieves that maximum.

sample

6
s1 s2 e1 s1 e2 e1
2
s1 e1
s2 e2

2 0