Trên đường quốc lộ, có ~n~ xe ô tô đi qua đường hầm một chiều. Các xe ô tô được đánh số từ ~1~ đến ~n~, mỗi xe đi vào và đi ra đường hầm với tốc độ không đổi. Ở đầu đường hầm và cuối đường hầm đều được gắn camera an ninh. Nhờ các camera an ninh mà cảnh sát giao thông biết được thứ tự các xe ô tô đi vào và ra khỏi đường hầm. Quy định giao thông nghiêm cấm các xe vượt nhau trong đường hầm. Nếu một xe i vượt một xe j trong đường hầm thì xe i sẽ bị phạt. Mỗi xe sẽ bị xử phạt một lần khi ra khỏi đường hầm nếu vượt bất kỳ một xe nào khác ở trong đường hầm. Xe i chắc chắn đã vượt xe j nếu xe i vào đường hầm sau xe j và đi ra khỏi đường hầm trước xe j.
Yêu cầu: Cho biết thứ tự đi vào và đi ra khỏi đường hầm của ~n~ xe ô tô, hãy đếm số lượng các xe bị phạt.
Dữ liệu vào:
Cho trong tệp văn bản TUNNEL.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương ~n~ là số lượng xe đi qua đường hầm.
- Dòng 2: Ghi ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ là thứ tự đi vào của các xe.
- Dòng 3: Ghi ~n~ số nguyên dương ~b_1, b_2, \dots, b_n~ là thứ tự đi ra của các xe.
Dữ liệu ra:
Ghi ra tệp văn bản TUNNEL.OUT theo cấu trúc:
- Dòng 1: ghi kết quả tìm được tương ứng với dữ liệu vào.
Ví dụ:
Input: TUNNEL.INP
5
3 5 2 1 4
4 3 2 5 1
Output: TUNNEL.OUT
2
Giải thích:
- Xe 4 vượt các xe: 1, 2, 3, 5 nên xe 4 bị phạt
- Xe 2 vượt 5 nên xe 2 bị phạt
Ràng buộc:
~(2 \leq n \leq 10^5; 1 \leq a_i, b_i \leq n; 1 \leq i \leq n)~.
Bình luận