Masala #0503

Xotira 32 MB Vaqt 1000 ms
14

Matematik Shoxjaxon

Shoxjaxon matematikaga juda qiziqadi. Shu sababli u do’stlariga ham yordamlashib turadi. Shoxjaxonning jami \(n\) nafar do’sti bor. U do’stlariga \(a[i]\) ta misol ishlab berishi mumkin. Do’stlari ko’pligi sababli u boshqacha yo’l tutdi. U bitta do’stini misolini ishlab berganidan so’ng shu do’stinikidan ko’p bo’lgan boshqa do’stini misolini ishlab berishi mumkin ya’ni \(a[i] < a[j] < a[k], …\) tartibida bo’lishi shart. Shunday qilib u eng ko’pi bilan nechta do’stiga yordam berishi mumkin.


Kiruvchi ma'lumotlar:

Kirish faylida birinchi qatorda Shoxjaxonning do’stlari soni \((2 ≤ n ≤ 2500)\). Keyingi qatorda \(n\) ta son \((0 ≤ a[i] ≤ 10000)\) kiritiladi.


Chiquvchi ma'lumotlar:

Chiqish faylida masalani javobi chiqarilsin


Misollar
# input.txt output.txt
1
8
4 0 3 2 7 1 8 9
5
Izoh:

1 – testga izoh:

Jami 8 nafar do’sti bor va ularning misollari soni keltirilgan. Shoxjaxon bu holatda 5 nafariga yordam bera oladi ya’ni: \([0, 3, 7, 8, 9]\). Bunda sonlar qatiy o’suvchi ketma-ketligida bo’lishi shart