USACO 2022 - US Open - Hạng Đồng

Nông dân John khao khát giành được giải thưởng bức ảnh con bò xuất sắc nhất tại hội chợ, đang cố gắng chụp bức ảnh hoàn hảo về \(N\) con bò của mình \((2 \leq N \leq 2*10^5, N\) chẵn\()\)

Nông dân John sở hữu \(2\) giống bò tiềm năng: Guernseys và Holsteins. Để làm cho bức ảnh của mình tốt nhất có thể, anh ấy muốn xếp những con bò của mình sao cho càng nhiều con bò Guernsey ở các vị trí chẵn trong hàng càng tốt (vị trí đầu tiên trong hàng là vị trí lẻ, tiếp theo là vị trí chẵn, ...). Do không giỏi giao tiếp với những con bò của mình, cách duy nhất để anh ta có thể đạt được mục tiêu là đảo ngược thứ tự của một dãy \(j\) con bò đầu tiên với \(j\) chẵn.

Hãy đếm số lần đảo ngược cần ít nhất để Nông dân John đạt được mục tiêu của mình.

Input

• Dòng đầu tiên chứa số \(N\).
• Dòng thứ hai chứa một xâu độ dài \(N\), theo thứ tự ban đầu của các con bò từ trái sang phải. Chữ H tượng trưng cho bò Holstein, trong khi chữ G tượng trưng cho bò Guernsey.

Output

In ra số lần đảo ngược tối thiểu cần thiết.

Scoring

• Subtask \(1\): \(N \leq 1000\).
• Subtask \(2\): Không có điều kiện gì thêm.

Example

14
GGGHGHHGHHHGHG

1

Con bò Bessie đang trốn đâu đó dọc theo trục số. Mỗi con bò khác trong số \(N\) con bò của nông dân John \((1\leq N\leq1000)\) đều có thông tin muốn chia sẻ: con bò thứ thứ \(i\) sẽ nói rằng Bessie hoặc đang trốn ở một địa điểm nào đó nhỏ hơn hoặc bằng \(p_i\), hoặc ở một địa điểm nào đó lớn hơn hoặc bằng \(p_i(0\leq p_i \leq 10^9)\).

Thật không may, có thể không có nơi trốn nào phù hợp với câu trả lời của tất cả con bò, nghĩa là không phải tất cả con bò đều nói sự thật. Đếm số con bò tối thiểu đang nói dối.

Input

• Dòng đầu tiên chứa số \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa L hoặc G, theo sau là số nguyên \(p_i\). L nghĩa là con bò thứ \(i\) nói rằng vị trí trốn của Bessie nhỏ hơn hoặc bằng \(p_i\), và G nghĩa là con bò thứ \(i\) nói rằng vị trí trốn của Bessie lớn hơn hoặc bằng \(p_i\).

Output

Số con bò tối thiểu đang nói dối.

Example

2
G 3
L 5

0

2
G 3
L 2

1

Luôn muốn tìm hiểu những thứ mới, cô bò Bessie đang học cách biến đổi kim loại. Cô ấy có \(a_i(0 \leq a_i \leq 10^4)\) miếng kim loại \(i\) \((1\leq i\leq N\leq100)\). Hơn nữa, cô ấy biết \(K(1\leq K\leq N)\) công thức để kết hợp một miếng của một số kim loại để tạo thành một miếng kim loại có chỉ số cao hơn tất cả các kim loại cấu thành. Ngoài ra, với mỗi kim loại, Bessie biết nhiều nhất một công thức chế tạo nó.

Tính số miếng kim loại \(N\) nhiều nhất Bessie có thể có được sau những phép biến đổi.

Input

• Dòng đầu tiên chứa số \(N\).
• Dòng tiếp theo chứa \(N\) số nguyên \(a_i\).
• Dòng thứ ba chứa số \(K\).
• \(K\) dòng tiếp theo bắt đầu bằng hai số nguyên \(L,M\) \((1\leq M)\), theo sau là \(M\) số nguyên. \(M\) số nguyên cuối cùng biểu thị các kim loại được dùng để tạo thành miếng kim loại \(L\). Dữ liệu đảm bảo rằng \(L\) lớn hơn \(M\) số nguyên cuối cùng.

Output

In ra số miếng kim loại \(N\) nhiều nhất Bessie có thể có sau khi áp dụng các phép biến đổi hoặc không làm gì.

Scoring

• Subtask \(1\): Một miếng kim loại \(i\) có thể biến thành miếng kim loại \(i+1\).
• Subtask \(2\): Mỗi công thức biến một miếng kim loại này thành một miếng kim loại khác.
• Subtask \(3\): Không có điều kiện gì thêm.

Example

5
2 0 0 1 0
3
5 2 3 4
2 1 1
3 1 2

1