P8986 [Peking University Training 2021] Gene Editing

CTT2021 D1T3

Humans have already developed many gene-editing techniques. One of the most traditional methods uses “restriction endonucleases” (restriction enzymes). Such enzymes can recognize specific nucleotide sequences and cut the phosphodiester bond connecting adjacent nucleotides at designated positions, producing sequence cuts called “ends”. Only matching ends can be ligated by DNA ligase. Suppose we want to use gene fragment $A$ to replace gene fragment $B$ on a vector $V$. In restriction-enzyme-based editing, the usual procedure is: 1. Choose one restriction enzyme recognition site at each end of gene $A$. These two recognition sites should also exist correspondingly at the two ends of gene $B$. 2. Use the restriction enzymes corresponding to the chosen recognition sites to process gene $A$, so that the corresponding ends are generated at both ends. Purify the processed gene $A$. 3. Use the same restriction enzymes to cut the recognition sites on vector $V$, separating gene $B$ from vector $V$. Purify the vector $V'$ with gene $B$ removed. 4. Mix vector $V'$ with gene $A$, and with the help of DNA ligase, reconnect the broken phosphodiester bonds. It is worth noting that if the two recognition sites produce the same ends after cutting, then in step 4 the vector $V'$ might ligate by itself, producing a vector that contains neither gene $A$ nor $B$; it is also possible that gene $A$ is inserted into $V'$ in reverse, also producing an incorrect vector. Therefore, in practice, restriction enzymes that produce different ends are usually chosen to process gene $A$ and vector $V$. In the year 3032, humans discovered an alien civilization HD1048576d that had mastered gene-editing technology. Of course, this technology only applies to the genes of alien organisms living on planet HD1048576d. The smallest unit that human gene-editing technology can recognize is a single base on a DNA sequence, while the alien civilization’s technology can recognize the smallest unit as a single noicleobase on their gene sequence. For convenience, we represent one noicleobase by a positive integer starting from $1$. Then an alien gene sequence can be represented as a corresponding sequence of positive integers. For an alien gene sequence of length $n$ (denote its positive-integer representation as $s_1, s_2, \cdots, s_n$), the gene-editing process of HD1048576d is as follows: 1. Choose an interval to be edited $[l, r]$, i.e. replace in place the subsequence $s_l, s_{l+1}, \cdots, s_r$ in the original sequence. 2. Pick an ordered pair of indices $(i, j)$ that crosses the interval to be replaced (i.e. $1\le i

The first line contains three positive integers $n, l, r$, representing the length of the gene sequence to be edited, the left endpoint of the region to be edited, and the right endpoint of the region to be edited. It is guaranteed that $3\le n\le 10^6$ and $1

If there exists a gene-sequence cutting plan that satisfies the constraints of the alien civilization’s gene-editing technology, output a positive integer, meaning among all valid plans, the minimum length of the cut-out gene subsequence. Otherwise, output `-1`, meaning that no cutting plan satisfies the constraints.

The optimal plan is to cut out `1 4 7 4 8 3`. It can be proved that there is no better cutting plan satisfying the technical constraints. A plan with a shorter cut length is `4 7 4 8 3`, but under this plan the specific recognition tool may cut out `4 8 3`, causing unexpected mutations in the resulting target gene sequence. Therefore, this cutting plan does not satisfy the technical constraints. --- For $100\%$ of the testdata, it is guaranteed that $3\le n \le 10^6$, $\forall 1\le i\le n, 1\le s_i\le 10^6$, and $1