Question
Cafeteria Lunch
The school cafeteria serves two types of sandwiches:
-
0 → circular
-
1 → square
Students stand in a queue, and sandwiches are arranged in a stack.
Each student has a preference (0 or 1), and the top sandwich of the stack is served first.
At each step:
-
If the student at the front likes the top sandwich, they take it and leave.
-
Otherwise, the student goes to the end of the queue.
This process continues until the sandwich on top is not wanted by any student left in the queue.
You are given:
-
an array
studentsrepresenting student preferences (front at index 0) -
an array
sandwichesrepresenting the sandwich stack (top at index 0)
Find the number of students who are unable to eat anything.
Input
The first line of input contains a single integer N representing the number of elements in the arrays.
The second line contains N space-separated integers representing the student preferences.
The third line contains N space-separated integers representing the sandwich types.
The second line contains N space-separated integers representing the student preferences.
The third line contains N space-separated integers representing the sandwich types.
Output
Print a single integer representing number of students that are unable to eat.
Example
Input
4
1 1 0 0
0 1 0 1
Output
0
Example
- Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1].
- Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0].
- Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,1].
- Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1].
- Front student takes the top sandwich and leaves the line making students = [] and sandwiches = [].
Hence all students are able to eat.
Input
4
1 1 1 0
0 0 0 0
Output
3
Explanation
Students: [1, 1, 1, 0]
Sandwiches: [0, 0, 0, 0]
Only the last student wants 0, the rest want 1.
Student 0, 1, and 2 keep rotating (want 1)
Eventually, student 3 gets their 0
Then no one wants the rest of the 0s
4
1 1 0 0
0 1 0 1
Output
0
Example
- Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1].
- Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0].
- Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,1].
- Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1].
- Front student takes the top sandwich and leaves the line making students = [] and sandwiches = [].
Hence all students are able to eat.
Input
4
1 1 1 0
0 0 0 0
Output
3
Explanation
Students: [1, 1, 1, 0]
Sandwiches: [0, 0, 0, 0]
Only the last student wants 0, the rest want 1.
Student 0, 1, and 2 keep rotating (want 1)
Eventually, student 3 gets their 0
Then no one wants the rest of the 0s