Given two sequences pushed and popped with distinct values, write a program to return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Problem Note

  • pushed is a permutation of popped.
  • pushed and popped have distinct values.

Example 1

Input: pushed = [5, 10, 15, 20, 25], popped = [20, 25, 15, 10, 5]
Output: 1
Explanation: We might do the following sequence:
push(5), push(10), push(15), push(20), pop() -> 20,
push(25), pop()-> 25, pop()-> 15, pop()-> 10, pop()-> 5

Example 2

Input: pushed = [5, 10, 15, 20, 25], popped = [20, 15, 25, 5, 10]
Output: 0
Explanation: 5 cannot be popped before 10.