시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB115360.000%

문제

Histogram je grafički prikaz statističke distribucije — funkcije koja svakom cijelom broju j između 1 i n pridružuje određenu vrijednost hj. Histogram crtamo tako da za svaki broj j nacrtamo stupac širine 1 i visine hj te sve takve stupce uredno posložimo na x-os slijeva nadesno počevši od ishodišta.

Slika 1: Histogram iz prvog primjera test podataka te sva tri moguća pravokutnika.

Zadan je histogram i prirodan broj p, odredite broj različitih pravokutnika R za koje vrijedi: vrhovi od R su točke s cjelobrojnim koordinatama, jedna stranica od R leži na x-osi, unutrašnjost od R je potpuno pokrivena histogramom i površina od R je barem p.

입력

U prvom redu nalaze se prirodni brojevi n i p — širina histograma i najmanja dozvoljena površina pravokutnika. U sljedećem redu nalazi se n prirodnih brojeva h1, h2, . . . , hn — vrijednosti distribucije predstavljene histogramom.

출력

Ispišite traženi broj pravokutnika.

서브태스크

번호배점제한
110

1 ≤ n ≤ 3 000, 1 ≤ p ≤ 1012, 1 ≤ hi ≤ 109

215

1 ≤ n ≤ 100 000, 1 ≤ p ≤ 108, 1 ≤ hi ≤ 1 000

315

1 ≤ n ≤ 100 000, p = 1, 1 ≤ hi ≤ 109

425

1 ≤ n ≤ 100 000, 1 ≤ p ≤ 100 000, 1 ≤ hi ≤ 109

535

1 ≤ n ≤ 100 000, 1 ≤ p ≤ 1014, 1 ≤ hi ≤ 109

예제 입력 1

6 9
1 4 4 5 2 3

예제 출력 1

3

예제 입력 2

10 5
3 6 1 3 2 1 5 3 4 2

예제 출력 2

31

채점 및 기타 정보

  • 예제는 채점하지 않는다.