Subtask 1

If there is an index ~i~ with ~s_i + 1 \ne s_{i+1}~, then these two elements must clearly belong to different subsequences. On the other hand, it always suffices to cut the permutation in between these indexes, since the subsequences formed will each be contiguous subsequences of ~t~, and thus can be rearranged to form ~t~. So the answer is ~1~ plus the number of such indexes.

Time complexity: ~\mathcal{O}(N)~

Subtask 2

With the same logic, the answer is ~1~ plus the number of indices where ~(s_i, s_{i+1})~ is not a contiguous subsequence of ~t~. This can be calculated fast by storing the adjacent pairs of elements of ~t~ in a set, or storing the index of each element in ~t~.

Time complexity: ~\mathcal{O}(N)~ or ~\mathcal{O}(N\log N)~