Bị sa thải

Điểm: 8,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Levian là kế toán tại một công ty lớn. Anh ấy biết thu nhập của công ty trong $n$ tháng liên tiếp — tháng thứ $i$ công ty có thu nhập $a_{i}$ (dương là lãi, âm là lỗ, $0$ là không đổi). Do tình hình bất ổn, thu nhập của $⌈ n / 2 ⌉$ tháng đầu có thể bất kỳ, nhưng từ tháng $⌈ n / 2 ⌉ + 1$ đến tháng $n$ thì thu nhập đều bằng nhau và bằng $x$ .

Levian sẽ báo cáo lên ban giám đốc $n - k + 1$ con số — tổng thu nhập trong mỗi $k$ tháng liên tiếp. Cụ thể, với mỗi $i$ từ $1$ đến $n - k + 1$ , anh ấy báo cáo giá trị $a_{i} + a_{i + 1} + \dots + a_{i + k - 1}$ .

Nếu có ít nhất một con số được báo cáo không phải là lãi (tức $\leq 0$ ), Levian sẽ bị sa thải.

Hãy cứu sự nghiệp của Levian: tìm một giá trị $k$ ( $1 \leq k \leq n$ ) sao cho mọi tổng $k$ tháng liên tiếp đều dương, hoặc báo là không tồn tại.

Dữ liệu vào

Dòng đầu chứa một số nguyên $n$ ( $2 \leq n \leq 5 \cdot 10^{5}$ ) — số tháng.
Dòng thứ hai chứa $⌈ n / 2 ⌉$ số nguyên $a_{1}, a_{2}, \dots, a_{⌈ n / 2 ⌉}$ ( $- 10^{9} \leq a_{i} \leq 10^{9}$ ) — thu nhập của các tháng đầu.
Dòng thứ ba chứa một số nguyên $x$ ( $- 10^{9} \leq x \leq 10^{9}$ ) — thu nhập mỗi tháng từ tháng $⌈ n / 2 ⌉ + 1$ đến tháng $n$ .

Dữ liệu ra

In ra một số nguyên $k$ thỏa mãn yêu cầu, hoặc $- 1$ nếu không tồn tại.

Nếu có nhiều đáp án hợp lệ, in ra giá trị nào cũng được.

Ràng buộc

$2 \leq n \leq 5 \cdot 10^{5}$
$- 10^{9} \leq a_{i}, x \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
3 2 -1 2	2	Dãy đầy đủ là $[2, - 1, 2]$ . Cả $k = 2$ (báo cáo $1, 1$ ) và $k = 3$ (báo cáo $3$ ) đều hợp lệ.
6 -2 -2 6 -1	4	Dãy đầy đủ là $[- 2, - 2, 6, - 1, - 1, - 1]$ . Với $k = 4$ các tổng là $1, 2, 3$ — tất cả dương.
5 2 2 -8 2	-1	Dãy đầy đủ là $[2, 2, - 8, 2, 2]$ . Không tồn tại $k$ nào để mọi tổng cửa sổ đều dương.

Bình luận

Không có bình luận tại thời điểm này.