dev — BOI contest
Task type: batch | Time limit: 2 s | Memory limit: 512 MB | Difficulty: 26
Algorithms: segment tree, coordinate compression, dynamic programming

# Task: DEV
## Developer

[![BOI](_page_0_Picture_1.jpeg)](_page_0_Picture_1.jpeg)
[![TORUŃ 2025](_page_0_Picture_2.jpeg)](_page_0_Picture_2.jpeg)

2025.04.27

You are in charge of developing new properties in the suburbs of Toruń. You have already decided that there will be one main street and *n* properties numbered from 1 to *n* along the street. The area is somewhat hilly, and the elevation of the *i*-th property is *a<sub>i</sub>* centimetres.

It turns out that no one wants to buy a property that is on a *slope*. Formally, for elevations *a*<sub>1</sub>, *a*<sub>2</sub>, ..., *a<sub>n</sub>*, a slope is a contiguous subsequence *a<sub>i-1</sub>*, *a<sub>i</sub>*, ..., *a<sub>j</sub>*, *a<sub>j+1</sub>* with 2 ≤ *i* ≤ *j* ≤ *n* - 1 such that either (i) *a<sub>i-1</sub>* < *a<sub>i</sub>* = *a<sub>i+1</sub>* = ... = *a<sub>j</sub>* < *a<sub>j+1</sub>*, or (ii) *a<sub>i-1</sub>* > *a<sub>i</sub>* = *a<sub>i+1</sub>* = ... = *a<sub>j</sub>* > *a<sub>j+1</sub>*. Intuitively, a slope is a contiguous range of properties at positions *i* - 1, *i*, *i* + 1, ..., *j*, *j* + 1, where the elevations of all properties at positions *i*, *i* + 1, ..., *j* are equal to some *h*, and *h* is strictly between *a<sub>i-1</sub>* and *a<sub>j+1</sub>*.

You are able to increase or decrease the elevation of any property by any integer, but of course you want to minimise the overall effort. Your task is to determine the minimal total change in elevation such that there are no slopes at all. That is, you want to find elevations *b*<sub>1</sub>, *b*<sub>2</sub>, ..., *b<sub>n</sub>* without slopes such that |*a*<sub>1</sub> - *b*<sub>1</sub>| + |*a*<sub>2</sub> - *b*<sub>2</sub>| + ... + |*a<sub>n</sub>* - *b<sub>n</sub>*| is as small as possible. The elevations *b<sub>i</sub>* must be integers (in particular, they don't have to be positive), and there are no other constraints on *b<sub>i</sub>*.

## Input

The first line contains an integer *n* (1 ≤ *n* ≤ 2 · 10<sup>5</sup>) denoting the number of properties along the street.

The second line contains *n* integers *a*<sub>1</sub>, *a*<sub>2</sub>, ..., *a<sub>n</sub>* (0 ≤ *a<sub>i</sub>* ≤ 10<sup>9</sup>), where the *i*-th integer *a<sub>i</sub>* is the initial elevation of the *i*-th property.

## Output

You should output the minimal total change in elevation to ensure that there are no slopes.

## Example

| Input               | Output |
| ------------------- | ------ |
| 11                  | 5      |
| 7 2 1 2 5 7 8 8 10 8 8 |        |

This is illustrated below. The dashed lines represent the changed elevations without slopes *b<sub>i</sub>* of their corresponding properties.

[![Figure 15](_page_0_Figure_15.jpeg)](_page_0_Figure_15.jpeg)
[![Figure 16](_page_0_Figure_16.jpeg)](_page_0_Figure_16.jpeg)

## Scoring

| Subtask | Constraints           | Points |
| ------- | --------------------- | ------ |
| 1       | *n* ≤ 5 and *a<sub>i</sub>* ≤ 10        | 4      |
| 2       | *n* ≤ 2000              | 13     |
| 3       | *a<sub>i</sub>* ≤ 10              | 8      |
| 4       | *a<sub>i</sub>* < *a<sub>i+1</sub>*           | 19     |
| 5       | *n* ≤ 2 ⋅ 10<sup>4</sup>     | 29     |
| 6       | No additional constraints. | 27     |

Starter code: