창의적 회계

사업의 이익을 회계 처리할 때, 연속된 날들을 고정된 크기의 구간으로 나누고 각 구간의 이익을 그 안에 있는 날들의 일일 이익을 모두 더한 값으로 계산할 수 있다. 예를 들어 주간 이익을 보려면 7일 구간을 고르면 된다. 구간의 시작 날짜도 자유롭게 고를 수 있다. 주간 이익을 계산할 때 일요일, 월요일, 심지어 수요일에 시작하는 주를 잡을 수 있다. 시작 날짜를 다르게 고르면 장부에 찍히는 이익의 모습이 바뀌고, 그에 따라 투자자에게 더 매력적으로 보이거나 덜 보이기도 한다.

예시로, 연속된 10일 동안의 이익(손실은 음수 이익으로 표기한다)을 3일 구간으로 나누면 다음과 같다.

$3, 2, {-7} \:|\: 5, 4, 1 \:|\: 3, 0, {-3} \:|\: 5$

이렇게 하면 이익이 $-2, 10, 0, 5$인 구간 네 개가 생긴다. 이 나눔에서는 고정 크기보다 짧은 부분 구간을 앞과 뒤에 둘 수 있다. 이익이 엄격하게 양수인 구간을 이익 구간이라고 한다. 위 예시에서 네 구간 중 이익 구간은 두 개뿐이다.

시작 날짜를 다르게 하면 다음과 같다.

$3, 2 \:|\: {-7}, 5, 4 \:|\: 1, 3, 0 \:|\: {-3}, 5$

이익이 $5, 2, 4, 2$인 구간 네 개가 생긴다. 네 구간 모두 이익 구간이므로 사업이 훨씬 꾸준해 보인다.

연속된 날들의 일일 이익 목록과 정수 범위가 주어진다. 그 범위 안에서 구간 크기를 임의로 고르고, 시작 날짜도 임의로 고를 수 있다면, 이익 구간의 개수는 최소 몇 개, 최대 몇 개가 될 수 있는가?

첫 줄에 공백으로 구분된 정수 세 개 $n$, $\ell$, $h$가 주어진다 ($1 \le \ell \le h \le n \le 3 \times 10^4$, $h - \ell \le 1\,000$). $n$은 장부에 기록된 날짜 수이고, $\ell$은 구간 크기의 최소 선택값, $h$는 최대 선택값이다.

이어지는 $n$개의 줄에는 각각 정수 $p$ ($-10^4 \le p \le 10^4$)가 하나씩 주어진다. 이들은 순서대로 나열된 일일 이익이다.

한 줄에 공백으로 구분된 정수 두 개 $min$과 $max$를 출력한다. $min$은 가능한 이익 구간 개수의 최솟값이고, $max$는 최댓값이다. 두 값 모두 $\ell$ 이상 $h$ 이하의 모든 구간 크기와 모든 시작 날짜에 대해 구한다.