MEXICO

`

Đề bài

Quandinh37 vừa được bố mẹ tặng một chiếc Macbook Pro 16 inch M2 Max cùng một voucher du lịch đến thành phố Guadalajara, Mexico. Trong lúc nghỉ dưỡng tại khách sạn, cậu tự nghĩ ra một bài toán thú vị như sau:

Trên con phố ở Guadalajara có \(n\) tòa nhà được đánh số từ \(1\) đến \(n\), mỗi tòa nhà có giá trị \(a_i\). Nhiệm vụ là đếm số cách chia dãy \(n\) tòa nhà thành các đoạn liên tiếp sao cho giá trị MEX của mỗi đoạn bằng nhau.

Giải thích:

• MEX (Minimum EXcluded): là số nguyên dương nhỏ nhất không xuất hiện trong tập. Ví dụ: MEX của \([0, 1, 2]\) là \(3\), của \([1, 2, 4]\) là \(0\).

Dữ liệu vào

• Dòng đầu chứa số nguyên \(n\) (\(1 \leq n \leq 3 \cdot 10^5\))
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) (\(1 \leq a_i \leq 10^9\))

Dữ liệu ra

• Một dòng duy nhất là số cách chia thỏa mãn yêu cầu, chia dư cho \(27102006\)

Sample Input

5
1 2 1 2 1

Sample Output

3

Giải thích

Có 3 cách chia thỏa mãn yêu cầu:

1. \([1; 5]\) (cả dãy có MEX giống nhau)
2. \([1,2]; [3,5]\)
3. \([1,3]; [4,5]\) ```