Balanced Tunnel (Codeforces 1237B)
Tags: Others, two pointers

Consider a tunnel on a one-way road. During a particular day, $$$n$$$ cars numbered from $$$1$$$ to $$$n$$$ entered and exited the tunnel exactly once. All the cars passed through the tunnel at constant speeds.A traffic enforcement camera is mounted at the tunnel entrance. Another traffic enforcement camera is mounted at the tunnel exit. Perfectly balanced.Thanks to the cameras, the order in which the cars entered and exited the tunnel is known. No two cars entered or exited at the same time.Traffic regulations prohibit overtaking inside the tunnel. If car $$$i$$$ overtakes any other car $$$j$$$ inside the tunnel, car $$$i$$$ must be fined. However, each car can be fined at most once.Formally, let's say that car $$$i$$$ definitely overtook car $$$j$$$ if car $$$i$$$ entered the tunnel later than car $$$j$$$ and exited the tunnel earlier than car $$$j$$$. Then, car $$$i$$$ must be fined if and only if it definitely overtook at least one other car.Find the number of cars that must be fined. 

Input: The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$), denoting the number of cars.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$), denoting the ids of cars in order of entering the tunnel. All $$$a_i$$$ are pairwise distinct.The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$), denoting the ids of cars in order of exiting the tunnel. All $$$b_i$$$ are pairwise distinct.

Output: Output the number of cars to be fined.

Note: The first example is depicted below:Car $$$2$$$ definitely overtook car $$$5$$$, while car $$$4$$$ definitely overtook cars $$$1$$$, $$$2$$$, $$$3$$$ and $$$5$$$. Cars $$$2$$$ and $$$4$$$ must be fined.In the second example car $$$5$$$ was definitely overtaken by all other cars.In the third example no car must be fined.

Sample Inputs:
5
3 5 2 1 4
4 3 2 5 1

7
5 2 3 6 7 1 4
2 3 6 7 1 4 5

2
1 2
1 2

Sample Outputs:
2

6

0

Solution (Python):
from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase

def solve(n, A, B):
    fined = set()
    i = 0
    j = 0
    while j < n:
        if A[i] in fined:
            i += 1
        elif A[i] == B[j]:
            i += 1
            j += 1
        else:
            fined.add(B[j])
            j += 1
    print(len(fined))

def main():
    n = int(input().strip())
    A = list(map(int, input().strip().split(' ')))
    B = list(map(int, input().strip().split(' ')))
    solve(n, A, B)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from sys import stdin, stdout
    n = int(stdin.readline())
    ent = [int(i) for i in stdin.readline().split()]
    exit = [int(i) for i in stdin.readline().split()]
    up = 0
    ans = n
    di = [0] * (n + 1)
    for i in range(n):
        di[exit[i]] = i + 1
    for i in range(n):
        posi = di[ent[i]]
        if posi > up:
            up = posi
            ans -= 1
    stdout.write(str(ans))
if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
ans = 0
(idx1, idx2) = (n - 1, n - 1)
visited = [False] * (n + 9)
while idx1 >= 0 and idx2 >= 0:
    if arr1[idx1] == arr2[idx2]:
        idx1 -= 1
        idx2 -= 1
    elif visited[arr2[idx2]]:
        idx2 -= 1
    else:
        ans += 1
        visited[arr1[idx1]] = True
        idx1 -= 1
print(ans)