Daft Trunk

Points: 1

Time limit: 1.0s

Memory limit: 256M

Problem type

Allowed languages

C, C++, Java, Python

Daft Trunk, the fab elephant DJ duo hailing from France, are producing their new album Random Access Mammoths. To get their signature trumpet sound, they rely on a synthesiser that outputs a sawtooth wave.

In synthesiser sound design, a sawtooth wave is represented by an array of integers denoting pitch values. To build up musical energy, a valid sawtooth wave's pitch increases sequentially (or stays flat), then drops sharply to start the next beat.

It is impossible for a sawtooth wave to drop in pitch, and then immediately drop again on the very next step. Formally, an array $a$ ~a~ is a valid sawtooth wave if there is no index $i$ ~i~ $(3 \le i \le n)$ ~(3 \le i \le n)~ such that $a_{i-2} > a_{i-1} > a_i$ ~a_{i-2} > a_{i-1} > a_i~.

Daft Trunk has discovered the art of sampling and found a rough audio sample consisting of $n$ ~n~ integers. In their mixing software, they have the ability to replace any pitch with any integer (even negative ones).

What is the absolute minimum number of replacements needed to make the audio sample a valid sawtooth wave? (If it is already a valid sawtooth wave, output 0).

Input

The first line contains a single integer $n$ ~n~ $(1 \le n \le 10^5)$ ~(1 \le n \le 10^5)~, the size of the audio sample.

The second line contains $n$ ~n~ integers $a_1, a_2, \dots, a_n$ ~a_1, a_2, \dots, a_n~ $(1 \le a_i \le 10^9)$ ~(1 \le a_i \le 10^9)~, the recorded pitch values.

Output

Output a single integer, the minimum number of replacements required to make the sample a valid sawtooth wave.

Example

Input 1

6
1 2 3 1 2 3

Output 1

The sample is already a valid sawtooth wave. The only drop occurs at $(3 \to 1)$ ~(3 \to 1)~, so there are no two consecutive drops. Therefore, $0$ ~0~ replacements are needed.

Input 2

5
5 4 3 2 1

Output 2

The pitch drops continuously. We can replace the $4$ ~4~ with a $6$ ~6~, and the $2$ ~2~ with a $4$ ~4~, making the array 5 6 3 4 1. The drops are now $(6 \to 3)$ ~(6 \to 3)~ and $(4 \to 1)$ ~(4 \to 1)~, which are completely separated by rises. This took $2$ ~2~ replacements.

Input 3

6
4 3 2 4 3 2

Output 3

Input 4

4
10 10 10 10

Output 4

Comments

0

Boblao commented on May 23, 2026, 6:49 a.m.

sybau x3

0

chinanumbawun commented on May 23, 2026, 6:19 a.m.

sybau

0

Big_Yuan commented on May 23, 2026, 6:03 a.m.

sybau

0

The_Michelers commented on May 23, 2026, 4:17 a.m.

hello ❤️️️❤️️️❤️️️❤️️️❤️️️❤️️️❤️️️️️