Đi chơi hội
Hôm nay làng có hội, ai nấy đều diện những bộ quần áo đẹp nhất để đi chơi. \(Kim\) cũng rất háo hức, cô đã chuẩn bị cho mình một bộ váy thật lộng lẫy và sẵn sàng hòa mình vào không khí vui tươi ngoài kia. Thế nhưng, niềm vui ấy nhanh chóng vụt tắt khi dì ghẻ đã ngăn lại.
Dì ghẻ, vốn không ưa \(Kim\), đã đưa cho cô một dãy số và ra điều kiện: \(Kim\) phải đếm xem trong dãy có bao nhiêu đoạn con liên tiếp mà số lượng số âm bằng số lượng số dương. Chỉ khi hoàn thành, cô mới được phép đi hội. \(Kim\) buồn bã nhìn vào dãy số rối rắm trước mặt, cảm thấy nhiệm vụ này dường như không thể thực hiện.
Liệu bạn có thể giúp Kim giải quyết bài toán khó nhằn này để cô kịp đi hội không?
Đầu vào
Dòng đầu tiên là số nguyên \(n\) thể hiện số lượng phần tử trong dãy. \((1 \le n \le 10^5)\)
Dòng thứ hai gồm \(n\) số nguyên \(A[i]\) thuộc dãy \(A\) mà dì ghẻ đã đưa cho \(Kim\). \((|A[i]| \le 10^9, A[i] \neq 0)\)
Đầu ra
Số nguyên duy nhất là kết quả của bài toán.
Ví dụ
Đầu vào
6
1 -2 3 -4 5 -6
Đầu ra
9
Giải thích
\(9\) đoạn con thỏa mãn là \((1, -2)\), \((-2, 3)\), \((3, -4)\), \((-4, 5)\), \((5, -6)\), \((1, -2, 3, -4)\), \((-2, 3, -4, 5)\), \((3, -4, 5, -6)\), \((1, -2, 3, -4, 5, -6)\).
Comments