问题描述

Ther Ther发明了一种新型的纸牌，被称作“神奇牌”，它洗牌的规则是这样的：纸牌从上到下的编号为“1、2、3……n”，要通过洗牌使从上到下的编号为“n、n-1……3、2、1”。

洗牌的规则是这样的，从原序列中随机抽出几张（个数可任意选），然后随机插到某个地方（当然也是任意选的）。如当有10张牌时，以下几步是合理的：

1 2 3 4 5 6 7 8 9 10——>1 2 5 6 7 8 3 4 9 10——>

1 8 3 4 9 2 5 6 7 10——>1 8 5 6 7 10 3 4 9 2……

现在有许多人（aoe、gh、xiang、Wyvernoid、ayliyh……）一起玩这种牌，每洗一次牌需要的时间都是1，Ther Ther当然希望自己最先完成洗牌。并且Ther Ther是个很懒的人，他当然希望自己能用最少的力气完成洗牌。如果从牌组中选K张牌放到其他地方，所需要的体力就是k。现在，轮到你来帮助Ther Ther了。请你告诉Ther Ther至少要用多少时间来完成洗牌，并告诉他在这个时间内完成洗牌所需要的最少体力。

输入格式

一个整数n，表示有n张牌。

输出格式

第一行一个整数表示所需要的最少时间。

第二行一个整数表示在这个时间内完成洗牌所需要的最少体力。

输入样例

3

输出样例

2
2

数据范围

对于20%的数据，n<=20；

对于50%的数据，n<=100；

对于100%的数据，n<=2000。