Хозяйка купален, Юбаба, стоит в начале моста и придирчиво осматривает своих работников. Из-за своего маленького роста она видит только тех духов, которые строго выше всех, кто стоит перед ними в очереди. Её ученик, Хаку, стоит в самом конце моста и следит за порядком с другой стороны. Он видит только тех духов, которые строго выше всех, кто стоит после них(ближе к Хаку).
Тихиро хочет, чтобы как можно больше её друзей-духов были замечены начальством и получили награду. У неё остался кусочек волшебного пирожка, подаренного Речным Божеством. Тихиро может отдать этот кусочек одному любому духу. Съев его, дух может изменить свой рост на любое целое положительное число.
Помогите Тихиро выбрать духа и новую высоту для него так, чтобы общее количество уникальных духов, которых увидят Юбаба или Хаку (или они оба), стало максимальным.
В первой строке вводится единственное число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$) — количество духов на мосту.
Во второй строке вводятся $$$n$$$ целых чисел $$$h_1, h_2...h_n$$$ ($$$1 \le h_i \le 10^9$$$) — начальные значения роста духов.
Выведите одно число — максимальное возможное количество духов, которые будут замечены Юбабой или Хаку после применения магии.
52 1 5 3 4
4
51 2 2 4 5
5
В первом примере Тихиро может дать пирожок второму духу. Второй дух меняет свой рост на 4, и теперь массив выглядит как [2, 4, 5, 3, 4]. Тогда духи с номерами 1, 2, 3 и 5 будут замечены.
Во втором примере третий дух меняет свою высоту на 3, и его начинает замечать Юбаба.
| Отбор на ВКОШП.Junior 2026 |
|---|
| Закончено |
