You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

街灯测试 (Streetlight Test)

题目描述

在一条笔直的街道上，有无数盏街灯，编号为 $1, 2, 3, \dots$。每盏街灯都有一个独立的开关。初始时，所有的灯都是熄灭的状态。

为了检验灯的质量，管理员想出了一个有趣的测试办法。他找了 $m$ 个人，让他们按顺序一个一个地从街道的一侧（编号 $1$ 的方向）进入。每个人都要遵循以下规则：

1. 从第 $1$ 盏灯开始检查。
2. 如果看到的灯是亮着的，就把它熄灭，然后继续走到下一盏灯。
3. 如果看到的灯是熄灭的，就把它点亮，然后停止任务（不再继续往后走，也不再操作后续的灯）。

现在请问，当第 $m$ 个人完成任务离开后，街道上有多少盏灯是亮着的？

输入格式

共一行，包含一个整数 $m$。

输出格式

共一行，一个整数，表示最后亮着的灯的数量。

样例 #1

样例输入 #1

3

样例输出 #1

2

样例输入 #2

5

样例输出 #2

2

数据范围

对于 20% 的数据，$m\leq100$。 对于50% 的数据，$m\leq 10^5$。 对于 100% 的数据，$0≤m\leq 2^{62}$（即在 64 位有符号整数范围内）。