#K79807. Maximizing Puzzle Satisfaction Score
Maximizing Puzzle Satisfaction Score
Maximizing Puzzle Satisfaction Score
You are given an integer n
and a list of n
integers representing variants of puzzles. You can rearrange the given puzzles in any order. The satisfaction score is defined as the number of times a participant receives a puzzle whose variant number is strictly greater than the variant number received by the participant immediately before them. In an optimal arrangement, the satisfaction score will be maximized.
Note: Based on the problem constraints and the optimal strategy, the answer is always n - 1. For example, if n = 5
, the maximum satisfaction score is 4
.
Your task is to compute this maximum possible satisfaction score.
inputFormat
The input consists of two lines:
- The first line contains a single integer
n
, indicating the number of puzzle variants. - The second line contains
n
space-separated integers representing the puzzle variants.
You are allowed to rearrange the puzzles in any order in order to maximize the satisfaction score.
outputFormat
Output a single integer representing the maximum possible satisfaction score, which is defined as the number of times a puzzle variant in the rearranged order is strictly greater than its immediately previous puzzle. Based on the optimal strategy, this value will be n - 1
.
5
1 2 3 4 5
4
</p>