USACO 2021 - Open - Gold - United Cows of Farmer John
Xem dạng PDF
Liên đoàn Bò sữa của bác John (UCFG) đang chuẩn bị phái một đoàn đại biểu tới International bOvine olympIad* (IOI).
Có ~N~ chú bò sẽ tham gia cuộc tuyển chọn cho đoàn đại biểu này ~(1 \le N \le 2 \cdot 10^5)~. Chúng đang xếp thành một hàng, với chú bò ~i~ có giống là ~b_i~.
Một đoàn đại biểu sẽ bao gồm một dãy bò liên tiếp có ít nhất hai con - hay nói cách khác, là những chú bò có số hiệu trong khoảng ~[l, r]~ với hai số nguyên ~l~ và ~r~ thỏa mãn ~1 \le l < r \le N~. Hai chú bò ở hai đầu của dãy đã được chọn sẽ làm "đội trưởng". Để tránh phối giống cận huyết, mỗi đội trưởng phải có giống khác với những chú bò còn lại (đội trưởng hay không là đội trưởng).
Hãy giúp UCFG đếm (cho mục đích đóng thuế) số lượng cách mà họ có thể chọn một đoàn đại biểu để phái tới IOI.
*International bOvine olympIad: Olympiad Bò Quốc tế.
Input
Dòng đầu tiên chứa số ~N~.
Dòng thứ hai chứa ~N~ số nguyên ~b_1,b_2,...,b_N~, trong khoảng ~[1, N]~.
Output
Ghi ra số lượng đoàn đại biểu có thể phái đi, trên một dòng.
Sample Input
7
1 2 3 4 3 2 5
Sample Output
13
Giải thích
Các cặp đội trưởng của các đoàn đại biểu thỏa mãn là: ~(1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7)~.
Ràng buộc
- Các test 1-3 thỏa mãn ~N \le 100~.
- Các test 4-8 thỏa mãn ~N \le 5000~.
- Các test 9-20 thỏa mãn ~N \le 200000~.
Bình luận
Bài tương tự nè mọi người : https://oj.vnoi.info/problem/bedaog07trip
https://ideone.com/wuF2Oj