冰岛包裹流通公司(The Icelandic Corporation for Parcel Circulation)是往返于冰岛与世界其他地区之间运输货物的主要承运商。他们最新的创新成果是一条连接欧洲大陆的无人机航线,有多架无人机沿着单一路线往返飞行。
Drone by Hyeri Kim, Pixabay
这些无人机配备了先进的系统,使它们能够在两架无人机靠近时进行避让机动。不幸的是,软件故障导致该系统瘫痪,现在所有的无人机都沿着航线飞行,且无法避免相互碰撞。
在本题中,无人机被视为沿着无限长直线以恒定速度运动的点。每当两架无人机处于同一位置时,它们就会发生碰撞,导致它们偏离飞行路径并坠入大西洋。题目保证无人机的飞行计划不会在任何时刻出现三架或更多无人机在同一位置碰撞的情况。
已知每架无人机当前的位置及其速度。你的任务是通过找出哪些无人机将无限期地继续飞行而不会坠毁,来评估系统故障造成的损失。
输入格式
输入包含:
- 一行一个整数 $n$ ($1 \le n \le 10^5$),表示无人机的数量。无人机编号从 $1$ 到 $n$。
- $n$ 行,第 $i$ 行包含两个整数 $x_i$ 和 $v_i$ ($-10^9 \le x_i, v_i \le 10^9$),表示第 $i$ 架无人机在无限长直线上的当前位置和速度。
无人机按 $x$ 坐标递增的顺序给出,且当前没有两架无人机处于同一位置,即对于每个 $i$,满足 $x_i < x_{i+1}$。你可以假设永远不会发生涉及三架或更多无人机的碰撞。
输出格式
输出永远不会坠毁的无人机数量,随后按编号递增的顺序输出这些无人机的索引。
样例
输入格式 1
3 10 15 30 5 50 -1
输出格式 1
1 3
输入格式 2
6 0 3 2 2 3 1 4 3 5 2 6 3
输出格式 2
2 1 6