张博士刚刚了解了MinX的概念,被MinX深深吸引,所以张博士决定立即使用MinX构建一个特殊的数组。
MinX的定义如下:一个非负整数集合的MinX值为不在该集合中的最小非负整数。例如:MinX ({1,2,3}) = 0; MinX ({0,1,2,4,5}) = 3。
现给定一个包含n个非负整数的数组a, 张博士想要创建一个新的数组b,其形式如下:
当a不为空时:
(1)选择一个整数k(1≤k≤|a|,|a|表示数组的长度,即数组中的元素个数)。
(2)将数组a的前k个整数的MinX值附加到数组b的末尾,并将前k个整数从数组a中删除。显然,|a|会同步减小。·
但是,由于张博士喜欢大数组和MinX概念一样多,所以张博士希望新数组b在字典结构上是最大的。所以,张博士让你告诉他,通过最优地构造数组可以创建的最大数组b是多少。
数组字典结构的大小关系定义如下:如果数组x和数组y的第一个元素值不同的位置为i(即前i-1个元素都相等)且有xi>yi,或者如果|x|>|y|且y是x的前缀(其中|x|表示数组x的大小),则数组x在字典结构上大于数组y。