5/3/26, 6:49 PM Problem - A - Codeforces
Shaheen_e_Iqbal | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS HACKS ROOM STANDINGS CUSTOM INVOCATION
Codeforces Round 987 (Div. 2)
A. Penchick and Modern Monument Finished
time limit per test: 1 second Practice
memory limit per test: 256 megabytes
Amidst skyscrapers in the bustling metropolis of Metro Manila, the newest Noiph mall in the
Philippines has just been completed! The construction manager, Penchick, ordered a state-of-
the-art monument to be built with n pillars. → Virtual participation
Virtual contest is a way to take part in past contest,
The heights of the monument's pillars can be represented as an array h of n positive as close as possible to participation on time. It is
integers, where hi represents the height of the i -th pillar for all i between 1 and n . supported only ICPC mode for virtual contests. If
you've seen these problems, a virtual contest is not
for you - solve these problems in the archive. If you
Penchick wants the heights of the pillars to be in non-decreasing order, i.e. hi ≤ hi+1 for all just want to solve some problem from a contest, a
virtual contest is not for you - solve this problem in
i between 1 and n − 1. However, due to confusion, the monument was built such that the the archive. Never use someone else's code, read
heights of the pillars are in non-increasing order instead, i.e. hi ≥ hi+1 for all i between 1 the tutorials or communicate with other person
during a virtual contest.
and n − 1.
Start virtual contest
Luckily, Penchick can modify the monument and do the following operation on the pillars as
many times as necessary:
→ Clone Contest to Mashup
Modify the height of a pillar to any positive integer. Formally, choose an index 1 ≤ i ≤ n
and a positive integer x . Then, assign hi := x.
→ Submit?
Help Penchick determine the minimum number of operations needed to make the heights of
the monument's pillars non-decreasing.
Language: GNU G++20 13.2 (64 bit, winlib
Input Choose
Choose File No file chosen
Each test contains multiple test cases. The first line contains the number of test cases t ( file:
1 ≤ t ≤ 1000 ). The description of the test cases follows.
Submit
The first line of each test case contains a single integer n (1 ≤ n ≤ 50 ) — the number of
pillars.
→ Contest materials
The second line of each test case contains n integers h1 , h2 , … , hn (1 ≤ hi ≤ n and
hi ≥ hi+1 ) — the height of the pillars. Announcement (en)
Please take note that the given array h is non-increasing. Tutorial (en)
Note that there are no constraints on the sum of n over all test cases.
Output
For each test case, output a single integer representing the minimum number of operations
needed to make the heights of the pillars non-decreasing.
Example
input Copy
3
5
5 4 3 2 1
3
2 2 1
1
1
output Copy
4
1
[Link] 1/2
5/3/26, 6:49 PM Problem - A - Codeforces
0
Note
In the first test case, the initial heights of pillars are h = [5, 4, 3, 2, 1] .
In the first operation, Penchick changes the height of pillar 1 to h1 := 2 .
In the second operation, he changes the height of pillar 2 to h2 := 2 .
In the third operation, he changes the height of pillar 4 to h4 := 4.
In the fourth operation, he changes the height of pillar 5 to h5 := 4 .
After the operation, the heights of the pillars are h = [2, 2, 3, 4, 4] , which is non-decreasing.
It can be proven that it is not possible for Penchick to make the heights of the pillars non-
decreasing in fewer than 4 operations.
In the second test case, Penchick can make the heights of the pillars non-decreasing by
modifying the height of pillar 3 to h3 := 2.
In the third test case, the heights of pillars are already non-decreasing, so no operations are
required.
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/03/2026 18:49:19UTC+5 (k3).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by
[Link] 2/2