Phái Đoàn Bò

Điểm: 1,00 (OI)

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

Python 3 5.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

Cho dãy $N$ con bò xếp thành hàng, con bò thứ $i$ thuộc giống $b_{i}$ . Một phái đoàn là một đoạn liên tiếp $[l, r]$ ( $l < r$ ) gồm ít nhất 2 con bò, trong đó hai con bò ở hai đầu ( $l$ và $r$ ) được chọn làm trưởng đoàn.

Điều kiện: Mỗi trưởng đoàn phải thuộc giống khác với tất cả các con bò còn lại trong phái đoàn. Cụ thể:

Giống của bò $l$ không xuất hiện trong đoạn $[l + 1, r]$
Giống của bò $r$ không xuất hiện trong đoạn $[l, r - 1]$

Hãy đếm số phái đoàn hợp lệ.

Dữ liệu vào

Dòng 1: Số nguyên $N$
Dòng 2: $N$ số nguyên $b_{1}, b_{2}, \dots, b_{N}$

Dữ liệu ra

Một số nguyên duy nhất: số phái đoàn hợp lệ.

Ràng buộc

$2 \leq N \leq 2 \times 10^{5}$
$1 \leq b_{i} \leq N$
Kết quả có thể cần kiểu 64-bit

Ví dụ

Input	Output	Giải thích
7 1 2 3 4 3 2 5	13	Có 13 cặp $(l, r)$ thỏa mãn. Ví dụ: $(1, 2)$ , $(2, 3)$ , $(4, 7)$ , v.v.

Bình luận

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