#P12429. [BalticOI 2025] Developer

[BalticOI 2025] Developer

题目描述

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 nn properties numbered from 1 to nn along the street. The area is somewhat hilly, and the elevation of the ii-th property is aia_i centimetres.

It turns out that no one wants to buy a property that is on a slope. Formally, for elevations a1,a2,,ana_1, a_2, \ldots, a_n, a slope is a contiguous subsequence ai1,ai,,aj,aj+1a_{i-1}, a_i, \ldots, a_j, a_{j+1} with 2ijn12 \leq i \leq j \leq n-1 such that either (i) ai1<ai=ai+1==aj<aj+1a_{i-1} < a_i = a_{i+1} = \ldots = a_j < a_{j+1}, or (ii) ai1>ai=ai+1==aj>aj+1a_{i-1} > a_i = a_{i+1} = \ldots = a_j > a_{j+1}. Intuitively, a slope is a contiguous range of properties at positions i1,i,i+1,,j,j+1i-1, i, i+1, \ldots, j, j+1, where the elevations of all properties at positions i,i+1,,ji, i+1, \ldots, j are equal to some hh, and hh is strictly between ai1a_{i-1} and aj+1a_{j+1}.

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 b1,b2,,bnb_1, b_2, \ldots, b_n without slopes such that a1b1+a2b2++anbn|a_1 - b_1| + |a_2 - b_2| + \ldots + |a_n - b_n| is as small as possible. The elevations bib_i must be integers (in particular, they don't have to be positive), and there are no other constraints on bib_i.

输入格式

The first line contains an integer nn (1n21051 \leq n \leq 2 \cdot 10^5) denoting the number of properties along the street.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (0ai1090 \leq a_i \leq 10^9), where the ii-th integer aia_i is the initial elevation of the ii-th property.

输出格式

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

11
7 2 1 2 5 7 8 8 10 8 8
5

提示

This is illustrated below. The dashed lines represent the changed elevations without slopes bi of their corresponding properties.

Scoring

Subtask Constraints Points
1 n5n \leq 5 and ai10a_i \leq 10 4
2 n2000n \leq 2000 13
3 ai10a_i \leq 10 8
4 ai<ai+1a_i < a_{i+1} 19
5 n2104n \leq 2 \cdot 10^4 29
6 No additional constraints. 27