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.

题目背景

我们怀念慢半拍的过去

我们失去慢半拍的勇气

精挑细选的心 洗也洗不干净

还好这世界早已那么褒贬不一

它让人歇斯底里 慢半拍的自己

我们剩下慢半拍的自己

在拥挤里耗尽 我们都硬着心

要面无表情的去接受惊喜

痛也毫不经意 避开致命问题

错过你美意

题目描述

青创班一年一度的足球比赛就要来了，作为足球爱好者的邓老师正在积极准备这场比赛。

现在邓老师遇到了一个难题。青创班的同学们组成了 $n$ 支队伍，但是由于时间问题，需要用尽可能少的比赛场次完成冠军的角逐，现在需要你帮助邓老师计算出，最少需要几场比赛才能找到最终的冠军。

• 不考虑队员的体力以及实力差距等等情况，只考虑比赛结果。

• 每一轮比赛可以选没有被淘汰的任意两支队伍进行比赛。

• 两个队伍进行比赛的结果只可能有胜和负两种，负的队伍淘汰，赢的队伍晋级。

• 当且仅当 $n-1$ 支队伍全部被淘汰，剩下的一支队伍就是冠军。

输入格式

一行一个整数 $n$， 表示一共有 $n$ 个队伍进行冠军的角逐。

输出格式

一行一个整数，表示最少需要的比赛轮数。

2

1

4

3

样例解释

对于样例1，只需要让参赛的两支队伍进行一次比赛就可以得出冠军。

对于样例2，我们假设四支队伍的编号是 $1,2,3,4$，一种可行的方案是，$1,2$ 比出胜者队，$3,4$比出胜者队，然后两支队伍比出冠军。可以证明，没有更优的方案。

数据范围

对于 $100\%$ 的数据，保证 $1\le n \le 1000$。