Thầy Nam muốn gửi một đội quân Droid đi thực hiện một nhiệm vụ quan trọng. Trước mặt thầy là một dãy n Droid, được đánh số từ 1 đến n từ trái sang phải. Nhưng thầy chỉ lấy ra một đoạn con liên tiếp để làm một đội. Nghĩa là, tất cả các Droid với các số từ l đến r đối với một số l và r (1 <= l <= r <= n). Mỗi Droid được đặc trưng bởi AIQ - hệ số trí tuệ nhân tạo của riêng nó. AIQ của số Droid i bằng ai.
Các Droid trong cùng một đội có thể kết hợp thành các Droid cao cấp hơn. Nếu có hai Droid có cùng AIQ là x trong đội, chúng có thể hợp nhất thành một Droid với AIQ là x + 1. Thầy Nam muốn chọn một đội để tất cả các Droid trong đội có thể, sau một số lần kết hợp, trở thành một Droid duy nhất. Giúp thầy Nam đếm số đoạn con khác nhau mà thầy có thể chọn làm một đội như mong muốn.
Định dạng đầu vào:
Định dạng đầu ra:
Ví dụ
AIQ.INP |
AIQ.OUT |
3 1 1 2 |
5 |
7 3 4 3 5 3 4 3 |
13 |