题目描述

栈是一种先进后出的数据结构。如一个栈的入栈序列为1 2 3 4，那么一种可能的进出栈顺序是：1In → 2In → 2Out → 3In → 4In → 4Out → 3Out → 1Out，于是出栈序列为2 4 3 1。

输入一个整数n，假设栈的入栈顺序为1~n，输出合法的出栈序列的个数。