33727번 - Just Long Neckties 2 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 171 | 18 | 14 | 10.294% |
문제
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:
- First, you ask the audience to call out a number of their choice. Let this number be $x$.
- Next, you decide whether to respond or ignore it.
- If you choose to respond to it, you must select one of the models on stage whose necktie length is currently less than or equal to $x$ and set the length of that model’s necktie to exactly $x$. (Note that you may select a model whose necktie length is already $x$.) However, if no model can be selected, the showcase event will fail.
- If you choose to ignore it, you 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.
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.
제한
- $2 ≤ N ≤ 5\, 000\, 000$.
- $1 ≤ A_i ≤ 21$ ($1 ≤ i ≤ N$).
- Given values are all integers.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 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. |
예제 입력 1
5 5 3 4 2 1
예제 출력 1
2
When $k = 2$, the showcase event can be conducted as follows, for example:
- First, two models wearing the new neckties appear on stage. Initially, the length of each model’s necktie is $1$.
- During the $1$st performance, the audience calls out $5$. You ignore this.
- During the $2$nd performance, the audience calls out $3$. You respond to this by selecting the first model and setting their necktie length to $3$. The necktie lengths of the two models are now $3$ and $1$, respectively.
- During the $3$rd performance, the audience calls out $4$. You respond to this by selecting the first model and setting their necktie length to $4$. The necktie lengths of the two models are now $4$ and $1$, respectively.
- During the $4$th performance, the audience calls out $2$. You respond to this by selecting the second model and setting their necktie length to $2$. The necktie lengths of the two models are now $4$ and $2$, respectively
- During the $5$th performance, the audience calls out $1$. You ignore this.
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.
예제 입력 2
6 2 1 1 2 2 1
예제 출력 2
1
When $k = 1$, the showcase event can be conducted as follows, for example:
- First, a model wearing the new necktie appear on stage. Initially, the length of the model’s necktie is $1$.
- During the $1$st performance, the audience calls out $2$. You ignore this.
- During the $2$nd performance, the audience calls out $1$. You respond to this by selecting the only model on stage and setting their necktie length to $1$.
- During the $3$rd performance, the audience calls out $1$. You respond to this by selecting the only model on stage and setting their necktie length to $1$.
- During the $4$th performance, the audience calls out $2$. You respond to this by selecting the only model on stage and setting their necktie length to $2$.
- During the $5$th performance, the audience calls out $2$. You respond to this by selecting the only model on stage and setting their necktie length to $2$.
- During the $6$th performance, the audience calls out $1$. You ignore this.
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.
예제 입력 3
10 2 4 6 7 4 5 5 3 4 1
예제 출력 3
3
This sample input satisfies the constraints of Subtasks 1, 4, 5, 6, and 7.
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호