MED-MEX
\(n\) бүтін сандардан тұратын массив \(a_1, a_2, \dots, a_n\) берілген.
Әрбір \(a_l, a_{l+1}, \dots, a_r\) қосмассиві үшін:
\(mex\) қосмассиві ретінде нөлден үлкен ең кіші бүтін санды анықтаймыз, ол осы қосмассивте жоқ.
\(median\) қосмассиві ретінде қосмассивтің элементтері өсу ретімен орналастырылғанда \(\left\lceil \frac{len}{2} \right\rceil\) позициясында тұрған санды анықтаймыз, мұнда \(len = r - l + 1\). Позициялардың нумерациясы \(1\)-ден басталады.
\(median = mex + 1\) теңдігі орындалатын қосмассивтердің санын есептеу қажет.
Енгізу
Бірінші жолда бүтін сан \(n\) (\(1 \le n \le 2000\)) жазылған.
Екінші жолда \(n\) бүтін сан \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)) жазылған.
Шығару
\(median = mex + 1\) теңдігі орындалатын қосмассивтердің санын көрсетіңіз.
Бағалау жүйесі
| Подзадача | Қосымша шектеулер | Балдар | Қажетті подзадачалар |
|---|---|---|---|
| \(0\) | Мысалдар | \(0\) | — |
| \(1\) | \(a_i \le 2\) | \(7\) | — |
| \(2\) | \(a\) — \(1,2,3,\dots,n\) пермутациясы | \(4\) | — |
| \(3\) | \(n \le 100\) | \(18\) | \(0\) |
| \(4\) | \(a_i \le 40\) | \(15\) | \(1\) |
| \(5\) | \(a_1 \le a_2 \le \dots \le a_n\) | \(15\) | \(2\) |
| \(6\) | \(n \le 500\) | \(21\) | \(0,1,2,3\) |
| \(7\) | Қосымша шектеулерсіз | \(20\) | \(1,2,3,4,5,6\) |
Мысалдар
Енгізу 1
5
1 2 3 2 1Жауап 1
5Ескертпелер
Дәл 5 қосмассив жарамды
l = 2, r = 2: қосмассив. MEX = 1 (1 саны жоқ), median = 2, шарт орындалады.
l = 2, r = 3: қосмассив. Сортировкадан кейін, median = 2, MEX = 1, шарт орындалады.
l = 2, r = 4: қосмассив. Сортировкадан кейін, median = 2, MEX = 1, шарт орындалады.
l = 3, r = 4: қосмассив. Сортировкадан кейін, median = 2, MEX = 1, шарт орындалады.
l = 4, r = 4: қосмассив. MEX = 1, median = 2, шарт орындалады.
Осылайша, жауап 5-ке тең