题目内容

某仓储中心中有一个货物堆放区，货物编号按乱序堆叠存放，只能从顶部取货（后进先出），管理员需要将货物按编号从小到大取出。

仓库设有 $1$ 个临时区，可将主库顶部货物依次转移到临时区，临时区也为堆叠存放（后进先出）；主库或临时区顶部货物均可直接出库；其他操作（包括主库→临时区 和 临时区→主库）均为“暂存”操作；请计算至少需要多少次暂存操作，能保证所有货物按编号从小到大依次出库。

补充说明：

• 临时区有且只有一个
• 出库顺序必须是严格升序，每件出库货物的编号必须大于前一件
• 题目保证所有货物编号互不重复（可能为负数，编号数字不保证连续）
• 题目保证总能找到一种合法的操作方案完成有序出库

输入描述

参数 $1$：一个整数 $n$（$1<n<1000$），表示货物的总数量。

参数 $2$：整数数组 $[a_1, a_2, \ldots, a_n]$（$-1000 < a_i < 1000$），表示货物的编号，从左到右依次对应货物堆底部到顶部。

输出描述

一个整数，表示最少暂存操作次数。

样例1

输入

[3,1,2]

输出

1

说明

• 货物堆初始状态（底部→顶部）：[$3$ 号, $1$ 号, $2$ 号]，顶部货物为 $2$ 号
• 目标出库顺序：$1$ 号 → $2$ 号 → $3$ 号
• 操作过程：
  1. 顶部是 $2$ 号，但目标需要 $1$ 号，将 $2$ 号暂存到临时区（暂存次数 = $1$）
  2. 顶部是 $1$ 号，直接出库 → 已出库：[$1$ 号]
  3. 临时区顶部是 $2$ 号，出库 → 已出库：[$1$ 号, $2$ 号]
  4. 货物堆顶部是 $3$ 号，出库 → 已出库：[$1$ 号, $2$ 号, $3$ 号]
• 最少暂存次数：$1$

样例2

输入

[1,2,3]

输出

2

说明

• 货物堆初始状态（底部→顶部）：[$1$ 号, $2$ 号, $3$ 号]，顶部货物为 $3$ 号
• 目标出库顺序：$1$ 号 → $2$ 号 → $3$ 号
• 操作过程：
  1. 顶部是 $3$ 号，但目标需要 $1$ 号，将 $3$ 号暂存（次数 = $1$）
  2. 顶部是 $2$ 号，但目标需要 $1$ 号，将 $2$ 号暂存（次数 = $2$）
  3. 顶部是 $1$ 号，直接出库
  4. 临时区顶部是 $2$ 号，出库
  5. 临时区顶部是 $3$ 号，出库
• 最少暂存次数：$2$

样例3

输入

[6,5,2,4,3,1]

输出

3

说明

• 货物堆初始状态（底部→顶部）：$[6,5,2,4,3,1]$，顶部为 $1$ 号
• 目标出库顺序：$1$ → $2$ → $3$ → $4$ → $5$ → $6$
• 操作过程：
  1. 主库顶部 $1$ 号，直接出库 → 主库：$[6,5,2,4,3]$，临时：$[]$
  2. 目标 $2$ 号在主库深度 $2$（上方隔着 $3$ 和 $4$），将 $3$、$4$ 暂存到临时区，暂存次数 = $2$ → 主库：$[6,5]$，临时：$[3,4]$（顶）
  3. 主库顶部 $2$ 号，直接出库 → 主库：$[6,5]$
  4. 目标 $3$ 号在临时区深度 $1$（上方隔着 $4$），将 $4$ 暂存回主库，暂存次数 = $3$ → 主库：$[6,5,4]$，临时：$[3]$（顶）
  5. 临时区顶部 $3$ 号，直接出库
  6. 主库顶部 $4$ 号，直接出库
  7. 主库顶部 $5$ 号，直接出库
  8. 主库顶部 $6$ 号，直接出库
• 最少暂存次数：$3$
• 关键：第 $4$ 步体现了双向暂存的价值 —— 将临时区的 $4$ 移回主库，释放 $3$ 出库。若无双向暂存，此场景无法解决。