#K79807. Maximizing Puzzle Satisfaction Score

    ID: 35390 Type: Default 1000ms 256MiB

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:

  1. The first line contains a single integer n, indicating the number of puzzle variants.
  2. 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.

## sample
5
1 2 3 4 5
4

</p>