Liên minh bò của Farmer John

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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 $N$ con bò xếp thành hàng, mỗi con thuộc một giống (breed) $b_{i}$ ( $1 \leq b_{i} \leq N$ ). Một đoàn đại biểu hợp lệ là cách chọn ba vị trí $l < m < r$ (gọi là ba lãnh đạo) sao cho:

$b_{l}$ , $b_{m}$ , $b_{r}$ đều khác nhau
Mỗi trong ba giống $b_{l}$ , $b_{m}$ , $b_{r}$ chỉ xuất hiện đúng một lần trong đoạn $[l, r]$

Đếm số đoàn đại biểu hợp lệ.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$ ( $1 \leq N \leq 2 \times 10^{5}$ ).

Dòng thứ hai chứa $N$ số nguyên $b_{1}, b_{2}, \dots, b_{N}$ ( $1 \leq b_{i} \leq N$ ).

Dữ liệu ra

Một số nguyên duy nhất (có thể lớn, cần dùng kiểu 64-bit).

Ràng buộc

$1 \leq N \leq 2 \times 10^{5}$
$1 \leq b_{i} \leq N$

Ví dụ

Input	Output	Giải thích
7 1 2 3 4 3 2 5	9	9 bộ ba lãnh đạo hợp lệ: $(1, 2, 3)$ , $(1, 2, 4)$ , $(1, 3, 4)$ , $(1, 4, 7)$ , $(2, 3, 4)$ , $(4, 5, 6)$ , $(4, 5, 7)$ , $(4, 6, 7)$ , $(5, 6, 7)$ (chỉ số 1-based).

Bình luận

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