| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 53 | 19 | 19 | 42.222% |
JOI mart is a shop which has N days of history. After opening JOI mart, the sales amount on the i-th day (1 ≤ i ≤ N) was Ai yen.
Bitaro is a shop manager of JOI mart, who will make a presentation of the financial report. For the presentation, he will choose some of the days, and show a bar chart of the sales amounts for the chosen days in chronological order. He will explain how the sales amounts changed for these days. In order to make the presentation much more impressive, he plans to choose the data for the presentation so that the presentation would give a better impression.
If Bitaro chooses the data of sales amounts for m days (1 ≤ m ≤ N) and he chooses the data of the p1, p2, . . . , pm-th days (1 ≤ p1 < p2 < · · · < pm ≤ N) after opening, the impression score of a bar chart is calculated as follows.
The impression score is equal to the number of times of making record-high sales amounts among the chosen days. In other words, the impression score is equal to the number of the indices j (1 ≤ j ≤ m) satisfying j = 1 or max{Ap1, Ap2, . . . , Apj−1} < Apj.
Bitaro wants to maximize the impression score, but the presentation might be unnatural for some choice of data. Thus, he decided to choose data satisfying both of the following conditions.
Write a program which, given the data of sales amounts of JOI mart after opening and an integer D, calculate the maximum of the impression score of a bar chart for the presentation.
Read the following data from the standard input. Given values are all integers.
N D A1 · · · AN
Write one line to the standard output. The output should contain the maximum of the impression score of a bar chart for the presentation.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 14 | N ≤ 20. |
| 2 | 14 | N ≤ 400. |
| 3 | 20 | N ≤ 7 000. |
| 4 | 12 | D = 1. |
| 5 | 5 | D = N. |
| 6 | 35 | No additional constraints. |
7 1 100 600 600 200 300 500 500
3
In this sample input, there are 7 possibilities for a bar chart for the presentation satisfying the conditions in the task statement.
Therefore, the maximum of the impression score is 3 points. Your program is considered correct if it outputs 3.
This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 6.
6 6 100 500 200 400 600 300
4
In this sample input, the maximum impression score is achieved if Bitaro shows a bar chart of the data of the 1, 3, 4, 5, 6-th days from opening. If these days are chosen, the sales amounts of the chosen days are 100, 200, 400, 600, 300 yen. Since the number of times of making record-high sales amounts among the chosen data is 4, the impression score is 4 points. Thus, output 4.
This sample input satisfies the constraints of Subtasks 1, 2, 3, 5, 6.
11 2 1 4 4 2 2 4 9 5 7 0 3
4
In this sample input, the maximum impression score is achieved if Bitaro shows a bar chart of the data of the 1, 3, 5, 6, 8, 9, 11-th days from opening, for example. If these days are chosen, the sales amounts of the chosen days are 1, 4, 2, 4, 5, 7, 3 yen. Since number of times of making record-high sales amounts among the chosen data is 4, the impression score is 4 points. Thus, output 4. Note that, in this sample input, there are several ways to choose the data satisfying the conditions in the task statements for which the impression score is 4 points.
This sample input satisfies the constraints of Subtasks 1, 2, 3, 6.