/*
设d[i]为以i结尾的最长上升子序列的长度，那么它的前一个元素是什么呢？
设它为j，则d[i] = max{d[j]} + 1，其中枚举条件是j < i且a[j] < a[i]。
状态有O(n)个，决策O(n)个，时间复杂度为O(n^2)。
下面考虑如何把它优化到O(nlogn)。
把同一个i对应的d[i]和a[i]看成一个二元组(d, a)。
在计算d[i]时，考虑所有满足j < i的二元组(d, a)。
显然它们的i是无关紧要的，只需要找出其中a[j] < a[i]的最大d[j]即可。
换句话说，程序看起来应该是这样的：
其中getmax(S,a[i])表示在集合S中所有a值小于a[i]的二元组中寻找d的最大值。
update(S,a[i],d[i])表示用二元组a[i]; d[i]更新集合S。
现在问题的关键是实现集合S。考虑二元组(5, 4)和(5, 3)。它们d值相同但a值不同。
对于后续决策来说，(5, 4)是合法时(5, 3)一定合法，而且(5, 4)和(5, 3)一样好。
因此我们规定：只保留(5, 3)！换句话说：d值相同的a只保留一个。
用g[i]表示d值为i的最小a，那么一定有g[1] < g[2] < …… < g[n]
（想一想，为什么？）。不存在的d值对应的g设为正无穷。
d[i]的计算可以使用二分查找得到大于等于a[i]的第一个数j，
则d[i] = j（本来是找不大于a[i]的最后一个数j，则d[i] = j + 1，
但这样转化后更方便）。g的更新由于g[j] > a[i]，且i的d值为j，
因此需要更新g[j] = a[i]。
程序如下：
fill (g , g + n , infinity );
for(int i = 0; i < n; i ++){
int j = lower_bound (g , g + n , a[ i ]) - g;
d[ i ] = j + 1;
g[ j ] = a[ i ];
}
6
1 6 2 4 3 7
*/
#include <iostream>
#define MAXN 500001
using namespace std;
int n, dp[MAXN], len, g[MAXN];
int binarySearch(int *M, int a) {
int left = 1, right = len, cnt = 0;
while(left <= right) {
int mid = (left + right) >> 1;
//= 适用于不降递增子序列
if(a >= M[ mid ]) {
if(cnt < mid) cnt = mid;
left = mid + 1;
}
else right = mid - 1;
}
return cnt;
}
void res() {
int cc, tmp;
len = 1; g[ 1 ] = dp[ 1 ];
//g[i] 表示 d值为i 的最小dp
for(int i = 2; i <= n; ++ i) {
tmp = binarySearch(g, dp[ i ]);
cc = tmp + 1;
if(cc > len) {
g[ cc ] = dp[ i ];
len ++;
}
else if(g[ cc ] > dp[ i ]) {
g[ cc ] = dp[ i ];
}
}
if(len > 1)
printf("My king, at most %d roads can be built.\n\n", len);
else
printf("My king, at most %d road can be built.\n\n", len);
}
int main() {
int z = 1, in;
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; ++ i) {
scanf("%d", &in);
scanf("%d", &dp[ in ]);
}
printf("Case %d:\n", z ++);
res();
}
return 0;
}