Leaders

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

Nông dân John có $N$ con bò ( $2 \leq N \leq 10^{5}$ ), mỗi con thuộc giống Guernsey (G) hoặc Holstein (H). Các con bò đứng thành hàng, đánh số từ $1$ đến $N$ .

Mỗi con bò $i$ viết ra một danh sách chứa các con bò từ vị trí $i$ đến vị trí $E_{i}$ ( $i \leq E_{i} \leq N$ ). FJ biết rằng mỗi giống bò có đúng một con thủ lĩnh, và danh sách của mỗi thủ lĩnh phải chứa tất cả các con bò cùng giống hoặc phải chứa thủ lĩnh của giống còn lại (hoặc cả hai).

Hãy đếm số cặp bò hợp lệ có thể làm thủ lĩnh (một con Guernsey và một con Holstein).

Dữ liệu vào

Dòng đầu: số nguyên $N$
Dòng thứ hai: xâu độ dài $N$ gồm các ký tự G và H
Dòng thứ ba: $N$ số nguyên $E_{1}, E_{2}, \dots, E_{N}$ cách nhau bởi dấu cách

Dữ liệu ra

In ra số cặp thủ lĩnh hợp lệ.

Ràng buộc

$2 \leq N \leq 10^{5}$
Luôn có ít nhất một con bò mỗi giống

Ví dụ

Input	Output	Giải thích
4 GHHG 2 4 3 4	1	Cặp hợp lệ duy nhất là $(1, 2)$ . Danh sách bò 1 chứa thủ lĩnh giống kia; danh sách bò 2 chứa tất cả Holstein.
3 GGH 2 3 3	2	Các cặp hợp lệ là $(1, 3)$ và $(2, 3)$ .

Bình luận

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