| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 164 | 16 | 12 | 9.302% |
Just Odd Inventions Co., Ltd. is a company renowned for doing ”just odd inventions.” Here we just call it JOI Company.
To celebrate the 5th anniversary of their flagship product, ”Just Long Neckties,” JOI Company has invented a new product: ”Just Stretchable Neckties.” As its name suggests, this new necktie has the unique feature of being able to 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, the length of every necktie worn by the models is set to 1ドル$.
After that, you will carry out a total of $N$ performances to demonstrate the necktie’s stretchable feature to the audience. Each performance is conducted as follows:
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.
The number of models on stage, denoted as $k$ ($k ≥ 1$), has not yet been determined. Since hiring models costs considerable money, it is desirable to keep $k$ as small as possible. The minimum value of $k$ required to prevent the showcase event from failing depends on the numbers called out by the audience during the performances. Fortunately, you possess precognitive abilities and have foreseen that the number called out by the audience during the $i$-th performance (1ドル ≤ i ≤ N$) will be $A_i$.
Write a program which, given the numbers called out by the audience during the showcase event, calculates the minimum number of models $k$ required to prevent the showcase event from failing.
Read the following data from the standard input.
$N$
$A_1$ $A_2$ $\cdots$ $A_N$
Write one line to the standard output. The output should contain the minimum number of models $k$ required to prevent the showcase event from failing.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N ≤ 15$. |
| 2 | 6 | $N ≤ 500,ドル $A_i ≤ 2$ (1ドル ≤ i ≤ N$). |
| 3 | 12 | $N ≤ 500,ドル $A_i ≤ 5$ (1ドル ≤ i ≤ N$). |
| 4 | 18 | $N ≤ 500,ドル $A_i ≤ 15$ (1ドル ≤ i ≤ N$). |
| 5 | 26 | $N ≤ 500,円 000,ドル $A_i ≤ 15$ (1ドル ≤ i ≤ N$). |
| 6 | 10 | $N ≤ 500,円 000$. |
| 7 | 18 | No additional constraints. |
5 5 3 4 2 1
2
When $k = 2,ドル the showcase event can be conducted as follows, for example:
When $k = 1,ドル the showcase event will always fail. For example, if you respond to the audience’s numbers during the 2ドル$nd, 3ドル$rd, and 4ドル$th performances as described above, the only model’s necktie length becomes 4ドル$ after the 3ドル$rd performance. Then, at the 4ドル$th performance, you cannot select a model whose necktie length is less than or equal to 2ドル,ドル so the showcase event fails.
Hence, the minimum number of models $k$ required to prevent the showcase event from failing is 2ドル,ドル and the output should be 2ドル$.
This sample input satisfies the constraints of Subtasks 1, 3, 4, 5, 6, and 7.
6 2 1 1 2 2 1
1
When $k = 1,ドル the showcase event can be conducted as follows, for example:
Note that in the example above, during the 2ドル$nd and 3ドル$rd performances, a model whose necktie length is already 1ドル$ is selected, and their necktie length is set to 1ドル$ again. Such a choice, where the necktie length does not change, is also allowed.
Hence, the minimum number of models $k$ required to prevent the showcase event from failing is 1ドル,ドル and the output should be 1ドル$.
This sample input satisfies the constraints of all the subtasks.
10 2 4 6 7 4 5 5 3 4 1
3
This sample input satisfies the constraints of Subtasks 1, 4, 5, 6, and 7.