You have always wanted to be a DJ and finally got your first opportunity! You have a list of songs
that you will play at a wedding in the order the songs appear in the list. Each song has a “fun level”
but the problem is that B&G (the bride and the groom) do not want any song to be played after a
song with a lower fun level, i.e., B&G consider the wedding playlist good only if the fun level of
the songs do not ever decrease. Fortunately, you can adjust the fun level of songs. You can choose
to change all songs with fun level x to fun level y, e.g., you can choose to change all songs with
fun level 10 to fun level 7 (or to fun level 18). Note that:
- When you choose to change all songs with fun level x to fun level y, even though all the
songs with fun level x are changed, this is considered as one change.
- When you choose to change all songs with fun level x, all the songs with fun level x change
and not a selected subset of the songs with fun level x.
- If you change all songs with fun level x to fun level y and then you decide to change all the
songs with fun level y to fun level z, the second change applies to the updated list and not
the original list. For example, if the original list is {… 3 … 8 … 3 … 8 … 3 …} and you
decide to change fun level 3 to 8 and then decide to change fun level 8 to 2, five songs
change their fun level to 2 and not two songs.
Given the order of the fun level of a list of songs, determine the minimum number of playlist
adjustments in the form of transforming all songs of levelxinto levely, such that the fun level of
the songs of the playlist is non-decreasing.
输入描述:
The first input line contains an integer,n(1≤n≤100,000), representing the number of songs in
the playlist. The following input line containsnspace separated integers, representing the fun
level for the songs in the order they appear in the playlist; each fun level is between 1 and
1,000,000,000 (inclusive).
输出描述:
Printthe minimum number of adjustments to make the playlist’s fun level non-decreasing.
示例1
说明
Explanation of the first Sample Input/Output:
One way to make the list non-decreasing is:
-Change all 7’s to 1
-Change all 8’s to 3
-Change all 5’s to 3
for a total of 3 changes.