Valid Stack Sequence

You are given a list of distinct integers pushes and another list of integers pops.

The values of pushes are pushed onto an empty stack in the given order. Between any two pushes, you may pop the stack any number of times. Return whether there is a way to interleave these pushes and pops so that the values popped, in order, are exactly pops, and every pushed value is eventually popped.

Note that pops must contain the same values as pushes, in some order, for the answer to be true. If the two lists have different lengths, or pops contains a value that was never pushed, the answer is false.

Examples

Example 1

Input: pushes = [1,2,3,4,5], pops = [4,5,3,2,1]
Output: true

Example 2

Input: pushes = [1,2,3,4,5], pops = [4,3,5,1,2]
Output: false

Example 3

Input: pushes = [], pops = []
Output: true