3130 - 致命相遇

题目描述

3023 年,人类终于实现了时空旅行,通过一条长达 100 米的时空隧道后,人们就可以在过去与未来之间进行穿梭。

现在有 n 名旅客在同一时空隧道进行时空旅行,回到过去向左,前往未来向右,他们在隧道中的移动速度是相同的。但是受限与时空效应,两名旅客迎面相遇时双方会同时掉头向相反方向前进。

不幸的是其中一名旅客感染了时空病毒,他在与其他旅客相遇时便会传染给该旅客。被感染后的旅客在和其他健康的旅客相遇后也会感染其他健康的旅客。假设感染后无法痊愈,且不影响行动速度。

时空管理局工作的你想知道当所有旅客都离开时空隧道时,有多少名旅客感染了时空病毒?

输入

第一行输入一个整数 n 表示旅客的数量。

接着的一行为 n 个用空格分隔的整数 P_1,P_2,\dots,P_n

P_i 的绝对值,表示旅客在初始状态下与隧道左侧端点的距离。P_i 如果是正数表示向右,负数表示向左。其中,第一个数据 P_1 代表了感染病毒的旅客。

输出

输出一个整数,表示感染病毒的旅客总数。

样例

输入

3
2 -4 6

输出

2

输入

6
8 -2 -4 10 -20 -12

输出

3

输入

8
10 8 5 1 -12 -20 -30 -50

输出

8
说明

【样例 1 解释】

一号旅客为感染源,向右前进,与向左行进的二号旅客相遇,将其感染,双方均掉头继续前进,均未与向右的三号旅客相遇,所以被感染的旅客数为 2

【数据范围】

1 < n < 50

-100 < P_i < 100

数据中不会出现 0,也不会出现两名旅客占用同一位置。

来源

东方博宜OJ

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 496
通过人数 124
金币数量 0 枚
难度 基础


上一题 下一题