Problems
Just Odd Inventions Co., Ltd. (JOI Company) is renowned for doing “just odd inventions.”
To celebrate the 5th anniversary of their flagship product, “Just Long Neckties,” JOI Company has invented a new product called “Just Stretchable Neckties.” As its name suggests, this new necktie can extend its length indefinitely.
JOI Company has decided to hold a showcase event to promote the new necktie, and you have been selected as the host of the event. At the event, several models wearing the new neckties will appear on stage. Initially, every model’s necktie length is set to 1.
After that, you will carry out a total of N performances to demonstrate the necktie’s stretchable feature. Each performance is conducted as follows:
First, ask the audience to call out an integer x of their choice.
Next, decide whether to respond or ignore it.
If you choose to respond, you must select one model on stage whose current necktie length is at most x, and set that model’s necktie length to exactly x. (Note that you may choose a model whose necktie length is already x.) However, if no such model exists, the showcase event will fail.
If you choose to ignore it, do nothing. However, if you ignore the audience’s number two or more times in a row, the audience will get angry, and the showcase event will fail.
Since hiring models is expensive, you wish to keep the number of models, k (k ≥ 1), as small as possible. The minimum number of models required to ensure the showcase event does not fail depends on the numbers called out by the audience during the performances. Fortunately, you have precognitive abilities and know in advance that the number the audience will call out in performance i (1 ≤ i ≤ N) is Aᵢ.
Your task is to determine, given A₁, A₂, …, A_N, the minimum number of models k required to prevent the showcase event from failing.
Input
The first line contains an integer N (2 ≤ N ≤ 5,000,000).
The second line contains N space-separated integers A₁, A₂, …, A_N (1 ≤ Aᵢ ≤ 21).
[Constrains]
2 ≤ N ≤ 5\ 000\ 000 1 ≤ A_i \le 21 (1 ≤ i ≤ N )Given values are all integers.
Output
Print a single integer on one line, the minimum number of models k required to prevent the showcase event from failing.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 10 | N ≤ 15 |
| #2 | 6 | N ≤ 500, Aᵢ ≤ 2 for 1 ≤ i ≤ N. |
| #3 | 12 | N ≤ 500, Aᵢ ≤ 5 for 1 ≤ i ≤ N |
| #4 | 18 | N ≤ 500, Aᵢ ≤ 15 for 1 ≤ i ≤ N |
| #5 | 26 | N ≤ 500,000, Aᵢ ≤ 15 for 1 ≤ i ≤ N |
| #6 | 10 | N ≤ 500,000 |
| #7 | 18 | No additional constraints |
Example #1
5
5 3 4 2 1
2
With k = 2 models, one possible strategy is:
Performance 1: Audience calls 5 → Ignore (first ignore is allowed).
Performance 2: Audience calls 3 → Respond by selecting model 1 and set necktie length to 3 (models' lengths: 3, 1).
Performance 3: Audience calls 4 → Respond by selecting model 1 and change necktie length to 4 (models' lengths: 4, 1).
Performance 4: Audience calls 2 → Respond by selecting model 2 and set necktie length to 2 (models' lengths: 4, 2).
Performance 5: Audience calls 1 → Ignore. Since the event does not fail, the minimum number of models required is 2.
Example #2
6
2 1 1 2 2 1
1
With just 1 model, the event can be conducted as follows:
Performance 1: Call 2 → Ignore.
Performance 2: Call 1 → Respond (model’s necktie remains 1).
Performance 3: Call 1 → Respond (model’s necktie remains 1).
Performance 4: Call 2 → Respond and update necktie length to 2.
Performance 5: Call 2 → Respond (neck tie remains 2).
Performance 6: Call 1 → Ignore. Thus, 1 model is sufficient.
Example #3
12
3 2 3 3 1 2 2 1 2 3 2 2
2
Example #4
12
4 5 1 3 5 2 1 3 3 1 2 2
3
You must sign in to write code.