MLE '19 Contest 4 P9 - Poggers - MCPT: Mackenzie Competitive Programming Team

MLE '19 Contest 4 P9 - Poggers

View as PDF

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 2.0s

Memory limit: 512M

Author:

Ninjaclasher

Problem type

An array $a$ ~a~ of $N$ ~N~ integers can be transformed into a new array through this process:

$a_i$ ~a_i~ is modified to be the maximum of $a_i$ ~a_i~ and $a_{i+1}$ ~a_{i+1}~ for all $1 \le i < N$ ~1 \le i < N~.

An array is stable if it remains the same after the above transformation is performed on the array. For example, $[2,1,1,1]$ ~[2,1,1,1]~ is a stable array.

It can be proven that array $a$ ~a~, after a certain number of transformations, will result in a stable array. Can you print out the minimum number of transformations on array $a$ ~a~ to transform it into a stable array?

Input Specification

The first line will contain the integer $N$ ~N~ $(1 \le N \le 10^5)$ ~(1 \le N \le 10^5)~.

The second line will contain the array $a$ ~a~ $(1 \le a_i \le 10^6)$ ~(1 \le a_i \le 10^6)~.

Output Specification

Output the number of minimum transformations to transform $a$ ~a~ into a stable array.

Sample Input

5
1 3 2 4 5

Sample Output

Comments

0

MstrPikachu commented on Dec. 30, 2019, 8:38 p.m.

How can $a_N$ ~a_N~ be modified to be the maximum of $a_N$ ~a_N~ and $a_{N+1}$ ~a_{N+1}~?

2

wleung_bvg commented on Dec. 31, 2019, 1:32 p.m.

$a_N$ ~a_N~ is never modified. Note that the problem statement mentions that we only modify $a_i$ ~a_i~ for $1 \le i < N$ ~1 \le i < N~.