TLEOJ Contest #10 - Dãy con chính phương

Điểm: 100 (thành phần)

Thời gian: 2.0s

Bộ nhớ: 512M

Input: bàn phím

Output: màn hình

Tác giả:

icebearlovecode

Dạng bài

Trong thủ đô Penguin có $n$ ngôi nhà, ngôi nhà thứ $i$ có mã định danh là $a_i$ . Sau khi đi dạo trong thủ đô, thị trưởng chinhoangmanutd nhận thấy các ngôi nhà không được đẹp nên nhờ jiangly kiểm tra xem có bao nhiêu dãy nhà liên tiếp có tổng mã định danh là một số chính phương để chinhoangmanutd đầu tư và nâng cấp. Sau khi tìm được kết quả, jiangly vui vẻ mang kết quả đến cho thị trưởng chinhoangmanutd nhưng do mãi xem màn trình diễn ảo thuật $chinh chong$ nên cậu đã quên mất kết quả là bao nhiêu. Bạn hãy giúp jiangly tìm lại kết quả đó nhé.

Input, Output và Subtask

Input

Dòng đầu tiên là số nguyên dương $n$ $(1 \le n \le 10^5)$ .
Dòng tiếp theo là dãy $a$ gồm $n$ phần tử $a_1, a_2, ..., a_n$ ( $1 \le a_i \le 10^2$ ).

Output

Gồm $1$ dòng duy nhất là kết quả thỏa mãn.

Subtask

Subtask $1$ $(50\%)$ : $1 \le n \le 100$ .
Subtask $2$ $(50\%)$ : Không có giới hạn gì thêm.

Example

Input

4
7 5 4 9

Output

Note

Có $5$ dãy có tổng là số chính phương là $[4], [9], [5, 4], [7, 5, 4], [7, 5, 4, 9]$ .

Bình luận

Không có bình luận nào.