P8446 Rainbow-colored Big Dipper

**[The background is unrelated to the problem and can be skipped; you may directly read the description.]** (This background is adapted from a real case.) Usami Renko is a college student from the Outside World. She majors in Super-Unified Physics at a university in Kyoto and has recently been doing research on string theory. Renko and Merry run a club called the Hifuu Club, carrying out activities to search for barriers scattered everywhere in the Scientific Century. This month, Merry and Renko again planned a new round of exploration, discovery, and hanging out together. But when they went out hand in hand, the sweet atmosphere was interrupted by a phone call. Because Renko often goes on adventures and spends time deepening her relationship with Merry, she kept delaying her homework. Her physics professor finally lost patience (after all, Renko had not written a single word of the physics homework she had拖了一个学期), and required her to submit a study report within $\sqrt9$ days before agreeing to file her “extracurricular practice activities.” Well, there was no choice (laugh). Renko could only try hard to patch together her study report before the deadline, and only then could they carry out their plan to watch the night sky.

Because the past two days were used by Renko to prepare for activities, she now only has a few minutes to patch together her assignment. Although this is not good, she has no other choice, so she can only extract a section from her previous class notes. Renko’s class notes have $n$ chapters, each recording different content. She can choose any contiguous segment $[l,r]$ (meaning she selects chapters $l$ through $r$) as the final result. The content of each chapter is different, and the teacher gives each chapter a rating score $a_i$. Since the study report should show the student’s progress, the teacher’s satisfaction will increase by the difference between the worst ( $\min\{a_i\}$ ) and the best chapter ( $\max\{a_i\}$ ) within the selected segment. However, directly submitting long class notes as a report looks too perfunctory, so for each chapter included, the teacher’s satisfaction will be $-1$. Formally, if Renko submits the notes on interval $[l,r]$, the teacher’s satisfaction is $\max\{a_l,a_{l+1},\cdots,a_r\}-\min\{a_l,a_{l+1},\cdots,a_r\}-(r-l+1)$. Renko wants you to help her find a plan that maximizes the teacher’s satisfaction. Since she is very smart, you only need to tell her this maximum satisfaction value, and she will know what to do. **[Formal statement]** You are given a sequence $a$ of length $n$. The value of a subarray $[l,r]$ is $\max\{a_l,a_{l+1},\cdots,a_r\}-\min\{a_l,a_{l+1},\cdots,a_r\}-r+l-1$. Find the subarray with the maximum value and output this value.

The first line contains a positive integer $n$, indicating the number of chapters in the notes. The second line contains the rating score sequence $a$, with elements separated by spaces.

Output the maximum satisfaction among all subarrays of the rating score sequence.

**[Sample explanation and notes]** Let $l=4,r=5$. Then $\min\{a_4,a_5\}=2$, $\max\{a_4,a_5\}=8$, and the contribution value is $4$. It is easy to prove that this is the subarray with the maximum satisfaction. **[Constraints]** - For $20\%$ of the testdata, $n\leq 5\times 10^3$. - For another $20\%$ of the testdata, all $a_i$ are equal. - For $100\%$ of the testdata, $1\le n\le 4\times10^6$, $1 \leq a_i \leq 10^9$. Translated by ChatGPT 5