B. Өсгөх ба бууруулах

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Поликарфусд $n$ ширхэг бүхэл тоонудыг агуулсан $a_{1}, a_{2}, ..., a_{n}$ массив байна. Поликарфус массивын элементүүдийг тэнцүүлж тоглох дуртай. Яагаад гэвэл тэр массивын аль болох олон элементийг тэнцүү байлгахыг хүсдэг. Үүний тулд Поликарфус дараах үйлдлийг хэд хэдэн удаа гүйцэтгэдэг:

  • тэр массивын $a_{i}$, $a_{j}$ $(i ≠ j)$ хоёр элементийг сонгоно;
  • тэр нэгэн зэрэг $a_{i}$ тоог $1$-ээр өсгөж, $a_{j}$ тоог $1$-ээр бууруулна, өөрөөр хэлбэл $a_{i} = a_{i} + 1$ ба $a_{j} = a_{j} - 1$.

Өгөгдсөн үйлдэл нь массивын яг хоёр ялгаатай элементийг өөрчилнө. Поликарфус тодорхойлогдсон үйлдлийг төгсгөлгүй удаа хийж чадна.

Хэрвээ тэр уг үйлдлийг дурын удаа гүйцэтгэсэн бол массивт хамгийн ихдээ хэдэн тэнцүү элемент байгааг мэдэхийг хүсэж байна. Поликарфусд тусал.

Оролт

Эхний мөр нь массивын хэмжээ $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоог агуулна. Хоёр дахь мөрөнд анхны массив болох зайгаар тусгаарлагдсан $a_{1}, a_{2}, ..., a_{n}$ ($|a_{i}| ≤ 10^{4}$) бүхэл тоонууд байна.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Тэр өгөгдсөн үйлдлийг дурын удаа гүйцэтгэсний дараа массивт байгаа тэнцүү элементийн хамгийн их тоо.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
2
2 1
Гаралт
1
Оролт
3
1 4 1
Гаралт
3
Сэтгэгдлүүдийг ачааллаж байна...