Dạng sóng tín hiệu
Đề bài
Mô tả
Trong một sứ mệnh liên sao nhằm giải mã các tín hiệu phát sóng của người ngoài hành tinh, Tiến sĩ Aurel đã thu được một tín hiệu năng lượng được biểu diễn bằng một mảng gồm số nguyên dương , trong đó là mức tần số tại chỉ số (). Ta định nghĩa là dãy thu được bằng cách gộp các phần tử giống nhau liên tiếp thành một phần tử duy nhất. Ví dụ, nếu thì .
Một phần tử của một dãy là cực đại địa phương chặt nếu giá trị của nó lớn hơn hẳn tất cả các phần tử kề với nó. Nó là cực tiểu địa phương chặt nếu giá trị của nó nhỏ hơn hẳn tất cả các phần tử kề với nó. Các phần tử ở biên của một dãy có độ dài chỉ có một phần tử kề. Trong một dãy có độ dài , phần tử duy nhất đồng thời vừa là cực tiểu địa phương vừa là cực đại địa phương.
Cho một bản ghi tín hiệu gốc gồm số nguyên dương. Một đoạn con liên tiếp với được gọi là một sóng rắn khi và chỉ khi mọi vị trí trong đều là cực tiểu địa phương chặt hoặc cực đại địa phương chặt.
Yêu cầu: Hãy đếm số cặp với sao cho đoạn con là một sóng rắn.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên ().
- Dòng thứ hai chứa số nguyên dương cách nhau bởi dấu cách ().
Dữ liệu ra
In ra một số nguyên duy nhất: số cặp hợp lệ.
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 1 2 4 4 3 3 |
11 | Các cặp hợp lệ là , , , , , , , , , , , tổng cộng cặp. Chẳng hạn không hợp lệ vì trong phần tử không phải cực trị; hợp lệ vì có độ dài . |
| 7 5 5 1 3 3 4 2 |
15 | Ví dụ bổ sung (không có trong đề gốc). Có cặp . Đoạn con hỏng khi chứa liền nhau (phần tử không phải cực trị), tức là và : có cặp như vậy. Đáp án là . |
Bình luận