← 返回题目列表

AtCoder · abc094_b

B. 收费站

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

有 N + 1 排成一排的方块,编号 0, 1, ..., N 从左到右。

最初,您位于 Square X。 您可以在相邻的广场之间自由移动。你的目标是到达 Square 0 或方形 N。 然而,对于每个 i = 1, 2, ..., M,广场有收费站 A_i,前往 Square A_i 产生的费用为 1。 保证广场没有收费站 0,方形 X 和广场 N.

找出达到目标之前发生的最小成本。

约束

  • 1 \leq N \leq 100
  • 1 \leq M \leq 100
  • 1 \leq X \leq N - 1
  • 1 \leq A_1 < A_2 < ... < A_M \leq N
  • A_i \neq X
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M X
A_1 A_2 ... A_M

输出

打印达到目标之前发生的最低成本。


示例输入 1

5 3 3
1 2 4

示例输出 1

1

最优解如下:

  • 一、从广场出发 3 到广场 4。这里,广场上有一个收费站 4,所以成本 产生了 1 。
  • 然后,从广场出发 4 到广场 5。这一次,没有产生任何费用。
  • 现在,我们在广场 5 我们已经达到了目标。

在这种情况下,产生的总成本是 1.


示例输入 2

7 3 2
4 5 6

示例输出 2

0

我们也许能够不付出任何代价就达到目标。


示例输入 3

10 7 5
1 2 3 4 6 8 9

示例输出 3

3