using System;
using System.Collections.Generic;
using System.Linq;
// PAST9回 嘘つきな生徒たち
// https://atcoder.jp/contests/past202112-open/tasks/past202112_l
class Program
{
static long[] GetSplitArr(string pStr)
{
return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
}
static void Main()
{
var TestData = new List<string>();
TestData.Add("5 5");
TestData.Add("4 3 3 1 0");
long Res = Solve(TestData);
Console.WriteLine(Res);
return;
var InsRandom = new Random();
for (int I = 1; I <= 30000; I++) {
int N = InsRandom.Next(2, 6);
int P = InsRandom.Next(N - 1, N + 3);
var RandList = new List<int>();
for (int J = 1; J <= N; J++) {
RandList.Add(InsRandom.Next(0, P));
}
var StrList = new List<string>();
StrList.Add(string.Format("{0} {1}", N, P));
StrList.Add(IntEnumJoin(" ", RandList));
long Result1 = SolveNaive(StrList);
long Result2 = Solve(StrList);
if (Result1 != Result2) {
Console.WriteLine("■■■差異あり■■■");
Console.WriteLine("愚直解={0}", Result1);
Console.WriteLine("高速解={0}", Result2);
StrList.ForEach(pX => Console.WriteLine(pX));
}
}
}
// セパレータとInt型の列挙を引数として、結合したstringを返す
static string IntEnumJoin(string pSeparater, IEnumerable<int> pEnum)
{
string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
return string.Join(pSeparater, StrArr);
}
static long SolveNaive(List<string> pInputList)
{
long[] wkArr = GetSplitArr(pInputList[0]);
long P = wkArr[1];
long[] AArr = GetSplitArr(pInputList[1]);
long UB = AArr.GetUpperBound(0);
var InsLinkedList = new LinkedList<JyoutaiDef>();
JyoutaiDef WillEnqueue;
WillEnqueue.CurrInd = -1;
WillEnqueue.CurrVal = P + 1;
WillEnqueue.Cost = 0;
InsLinkedList.AddFirst(WillEnqueue);
long Answer = long.MaxValue;
var EdakiriDict = new Dictionary<long, long>();
while (InsLinkedList.Count > 0) {
JyoutaiDef Dequeued = InsLinkedList.First.Value;
InsLinkedList.RemoveFirst();
if (Answer <= Dequeued.Cost) continue;
if (Dequeued.CurrVal < 0) continue;
// クリア判定
if (Dequeued.CurrInd == UB) {
Answer = Math.Min(Answer, Dequeued.Cost);
continue;
}
// 枝切り
long RestMinus = UB - Dequeued.CurrInd;
if (Dequeued.CurrVal - RestMinus < 0) continue;
long Hash = Dequeued.CurrInd;
if (EdakiriDict.ContainsKey(Hash)) {
if (EdakiriDict[Hash] >= Dequeued.CurrVal) {
continue;
}
}
EdakiriDict[Hash] = Dequeued.CurrVal;
// 変換しない場合
if (Dequeued.CurrVal > AArr[Dequeued.CurrInd + 1]) {
WillEnqueue.CurrInd = Dequeued.CurrInd + 1;
WillEnqueue.CurrVal = AArr[Dequeued.CurrInd + 1];
WillEnqueue.Cost = Dequeued.Cost;
InsLinkedList.AddFirst(WillEnqueue);
}
// 変換する場合
WillEnqueue.CurrInd = Dequeued.CurrInd + 1;
WillEnqueue.CurrVal = Dequeued.CurrVal - 1;
WillEnqueue.Cost = Dequeued.Cost + 1;
InsLinkedList.AddLast(WillEnqueue);
}
return Answer;
}
struct JyoutaiDef
{
internal long CurrInd;
internal long CurrVal;
internal long Cost;
}
// セパレータとInt型の列挙を引数として、結合したstringを返す
static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
{
string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
return string.Join(pSeparater, StrArr);
}
static long Solve(List<string> pInputList)
{
long[] wkArr = GetSplitArr(pInputList[0]);
long P = wkArr[1];
long[] AArr = GetSplitArr(pInputList[1]);
long UB = AArr.GetUpperBound(0);
// 値の下限以外を設定
long CurrJyougen = P;
var ValueInfoList = new List<ValueInfoDef>();
for (long I = 0; I <= UB; I++) {
var WillAdd = new ValueInfoDef();
WillAdd.CurrVal = AArr[I];
WillAdd.Jyougen = CurrJyougen--;
WillAdd.Distance = AArr[I] + I;
ValueInfoList.Add(WillAdd);
}
// 値の下限を設定
long CurrKagen = 0;
for (long I = UB; 0 <= I; I--) {
ValueInfoList[(int)I].Kagen = CurrKagen++;
}
// 値が範囲内な要素のみ残す
ValueInfoList = ValueInfoList.FindAll(pX => pX.Kagen <= pX.CurrVal && pX.CurrVal <= pX.Jyougen);
// LISを求める用のList
var LisList = ValueInfoList.Select(pX => pX.Distance).ToList();
LisList.Reverse();
long LISLength = ClassDeriveLISLength.DeriveLISLength(LisList, false);
return AArr.Length - LISLength;
}
class ValueInfoDef
{
internal long CurrVal; // 初期値
internal long Kagen; // 値の下限(狭義単調減少とする必要条件)
internal long Jyougen; // 値の上限(狭義単調減少とする必要条件)
internal long Distance; // 直交座標での原点からのマンハッタン距離
}
}
#region ClassDeriveLISLength
// LISの長さを返す
internal class ClassDeriveLISLength
{
// 引数1 long型の列挙
// 引数2 狭義か広義か？
// 戻り値 LISの長さ
internal static long DeriveLISLength(IEnumerable<long> pEnum, bool pIsStrict)
{
// LISの最終値の最小値[LISの長さ] なDP表
var DPSortedList = new SortedList<long, long>();
foreach (long EachVal in pEnum) {
if (DPSortedList.Count == 0) {
DPSortedList[1] = EachVal;
continue;
}
long UpsertKeyInd = ExecNibunhou(DPSortedList, EachVal, pIsStrict);
long CurrUB = DPSortedList.Count - 1;
var Keys = DPSortedList.Keys;
// 更新する位置によって分岐
if (UpsertKeyInd <= CurrUB) {
DPSortedList[Keys[(int)UpsertKeyInd]] = EachVal;
}
else {
long PrevKey = Keys[(int)CurrUB];
DPSortedList[PrevKey + 1] = EachVal;
}
}
if (DPSortedList.Count == 0) return 0;
return DPSortedList.Keys.Max();
}
// 二分法で、引数の値を設定する、キーの配列の添字を返す
private static long ExecNibunhou(SortedList<long, long> pDPSortedList, long pTargetVal, bool pIsStrict)
{
long UB = pDPSortedList.Count - 1;
var Keys = pDPSortedList.Keys;
if (pIsStrict) {
// 最小値以下の場合
if (pTargetVal <= pDPSortedList[Keys[0]]) return 0;
}
else {
// 最小値未満の場合
if (pTargetVal < pDPSortedList[Keys[0]]) return 0;
}
if (pIsStrict) {
// 最大値超えの場合
if (pTargetVal > pDPSortedList[Keys[(int)UB]]) return UB + 1;
}
else {
// 最大値以上の場合
if (pTargetVal >= pDPSortedList[Keys[(int)UB]]) return UB + 1;
}
long L = 0, R = UB;
while (L + 1 < R) {
long Mid = (L + R) / 2;
if (pIsStrict) {
if (pDPSortedList[Keys[(int)Mid]] <= pTargetVal) L = Mid;
else R = Mid;
}
else {
if (pDPSortedList[Keys[(int)Mid]] < pTargetVal) L = Mid;
else R = Mid;
}
}
return R;
}
}
#endregion