632. Build an Array With Stack Operations

You read the integers 1, 2, 3, ... in order from a stream. Using "Push" (push the next integer onto a stack) and "Pop" (remove the top), build a stack whose contents exactly equal the strictly increasing array target (a subsequence of 1..n). Return the list of operations. The input is JSON {target, n}.

Input: JSON {target, n}.

Output: Array — the sequence of "Push"/"Pop" operations.

Examples

Input: {"target":[1,3],"n":3}
Output: ["Push","Push","Pop","Push"]
Explanation: Push 1, push 2 then pop it, push 3.

Input: {"target":[1,2,3],"n":3}
Output: ["Push","Push","Push"]
Explanation: No pops needed.

Input: {"target":[2,3,4],"n":4}
Output: ["Push","Pop","Push","Push","Push"]
Explanation: Skip 1 with a pop.

Constraints

• 1<=target<=n<=100
• target strictly increasing

Asked by