E. Миша ба палиндромын зэрэг

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

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

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

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

Мишад гишүүд нь $1$-ээс $n$ хүртэл дугаарлагдсан бүхэл тоон дараалал өгөгджээ. Дарааллын $l$-ээс $r$ хүртэлх дугаартай гишүүдийг ямар нэгэн байрлалд оруулан $a$ дарааллыг палиндром болгож чаддаг байх $(l, r)$ $(1 ≤ l ≤ r ≤ n)$ хосуудын тоог $a$ дарааллын Палиндромын Зэрэг гэж тодорхойлъё. Өөрөөр хэлбэл $(l, r)$ хосын хувьд дарааллын $l$-ээс $r$ хүртэлх дугаарын гишүүдийн байрыг солих замаар (байрыг нь солихгүй байсан ч болно) дурын $1 ≤ i ≤ n$ бүрийн хувьд $a_i = a_{n-i+1}$ нөхцөл биелэх ёстой.

Чиний даалгавар бол Мишагийн дарааллын палиндромын зэргийг олох юм.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 10^{5}$) байрлана.

Хоёрдахь мөрөнд Мишагийн дарааллын гишүүд болох $a_i$ ($1 ≤ a_i ≤ n$) гэсэн $n$ ширхэг бүхэл тоо зайгаар тусгаарлагдсан байна.

Гаралт

Бодлогын хариуг хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
3
2 2 2
Гаралт
6
Оролт
6
3 6 5 3 3 5
Гаралт
0
Оролт
5
5 5 2 5 2
Гаралт
4

Тэмдэглэл

Эхний жишээн дээр бүх $(l, r)$ хос нөхцлийг хангана.

Гурав дахь жишээн дээр $(1, 3), (1, 4), (1, 5), (2, 5)$ хосууд нөхцлийг хангана.

Сэтгэгдлүүдийг ачааллаж байна...