Những Ngọn Núi

Điểm: 1,00 (OI)

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

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ ngọn núi đặt cách đều nhau với độ cao $h_{1}, h_{2}, \dots, h_{N}$ . Hai ngọn núi $i$ và $j$ ( $i < j$ ) có thể nhìn thấy nhau nếu không có ngọn núi $k$ nào ( $i < k < j$ ) nằm phía trên đoạn thẳng nối đỉnh hai ngọn núi.

Sau mỗi trong $Q$ lần cập nhật (tăng độ cao một ngọn núi), hãy đếm số cặp ngọn núi nhìn thấy nhau.

Dữ liệu vào

Dòng 1: số nguyên $N$ ( $1 \leq N \leq 2000$ ).
Dòng 2: $N$ số nguyên $h_{1}, \dots, h_{N}$ ( $0 \leq h_{i} \leq 10^{9}$ ).
Dòng 3: số nguyên $Q$ ( $1 \leq Q \leq 2000$ ).
$Q$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $x$ và $y$ ( $1 \leq x \leq N$ , $1 \leq y$ ) — tăng $h_{x}$ thêm $y$ .

Dữ liệu ra

In $Q$ dòng, mỗi dòng chứa số cặp ngọn núi nhìn thấy nhau sau lần cập nhật tương ứng.

Ràng buộc

$N, Q \leq 2000$
$0 \leq h_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
5 2 4 3 1 5 3 4 3 1 3 3 2	7 10 7	Ban đầu 6 cặp nhìn thấy nhau. Sau cập nhật 1 ( $h_{4} = 4$ ): 7 cặp. Sau cập nhật 2 ( $h_{1} = 5$ ): 10 cặp. Sau cập nhật 3 ( $h_{3} = 5$ ): 7 cặp.

Bình luận

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