Lần đầu trung bình vượt mốc (First Prefix Average Above Threshold)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho $n$ số nguyên $a_1,\ldots,a_n$ và mốc nguyên $T$. Tìm vị trí nhỏ nhất $i$ tính từ 1 sao cho trung bình cộng của $a_1$ đến $a_i$ lớn hơn nghiêm ngặt $T$. Nếu không có vị trí thỏa mãn, in -1.

Input

Dòng đầu chứa $n,T$. Dòng tiếp theo chứa đúng $n$ số nguyên theo thứ tự $a_1$ đến $a_n$.

Output

In một số nguyên là vị trí đầu tiên (đánh số từ 1), hoặc -1.

Subtask

• Subtask 1 (20%): $1\le n\le10$, $|T|\le10$, $|a_i|\le10$.
• Subtask 2 (30%): $1\le n\le1000$, $|T|\le1000$, $|a_i|\le1000$.
• Subtask 3 (50%): $1\le n\le10^5$, $|T|\le10^6$, $|a_i|\le10^4$.

Ví dụ

Ví dụ 1

Input

4 3
1 2 9 0

Output

3

Giải thích

Tiền tố i=1 có tổng1, trung bình1; i=2 có tổng3, trung bình1.5; i=3 tổng12, trung bình4>3. Vị trí đầu tiên là 3.

Ví dụ 2

Input

3 5
5 5 5

Output

-1

Giải thích

Trung bình mọi tiền tố bằng 5, không lớn hơn 5.