Subtask 1

This subtask is meant to reward brute-force solutions that run in ~\mathcal{O}(N^2)~, such as unoptimized versions of the full solution.

Subtask 2

The idea is to fix each index one by one to match Shinomiya's schedule. Since all courses in Shirogane's schedule are distinct, we can use a hash map to track the index of each course. Then, iterate from left to right. At each index ~i~, if ~A_i = B_i~, continue. Otherwise, find the index ~j~ such that ~A_j = B_i~ using the hash map and swap ~A_i~ and ~A_j~. After each swap, update the affected indices in the map.

This approach runs in ~\mathcal{O}(N)~ time using constant-time hash lookups.

Subtask 3

To deal with duplicate courses, map each course to a set of indices where it occurs. Again, iterate from left to right. For each index ~i~, if ~A_i = B_i~, do not swap anything. Otherwise, look for an occurrence of ~B_i~ in ~A~ that is after index ~i~ using the map, and swap with it. Then, update the affected indices in the sets. After processing each index ~i~, immediately remove it from the set that contains it to ensure it is never swapped again.

Note that other data structures may be used instead of a set, such as a priority queue or monotonic stack.

This approach runs in either ~\mathcal{O}(N)~ or ~\mathcal{O}(N\log{N})~, depending on the data structure used.