Rostoucí matice

Váš nejlepší kamarád vám pyšně ukázal svojí celočíselnou matici A, kterou v karanténě vyrobil. Zajímavé na ní je, že je po řádcích i sloupcích rostoucí, tj. A[r+1,s] > A[r,s] a A[r,s+1] > A[r,s] pro všechna smysluplná r a s. Vás by zajímalo, zda existuje nějaký řádek r a sloupec s takový, že A[r,s] = r+s. Kvalita vaší videokonference ale není moc valná, takže jednotlivé prvky matice nepřečtete. Proto se vždy vašeho kamaráda na nějaké políčko zeptáte a on vám ho nahlas přečte. Vaším cílem je samozřejmě najít hledané políčko (nebo zjistit, že neexistuje) na asymptoticky co nejméně dotazů.

Bonusové body můžete dostat, pokud dokážete, že množství dotazů, které vaše řešení provede, je až na konstantní faktor optimální.