На правилен многуаголник со N темиња, темињата се означени со некој позитивен цел број од 1 до 1 000 000 000. За секое теме (од првото до N-тото), на влез е даден соодветниот број А_i.

Задачата на Блерим е да ги поврзе со црвени отсечки (дијагонали или страни) сите темиња кои имаат иста вредност.

Ваша задача е за секое теме да утврдите колку е долга најдолгата отсечка што ќе излегува од него. За полесно пресметување ќе дефинираме дека: Отсечката е долга колку помалиот број на темиња кои се наоѓаат меѓу темињата кои таа ги поврзува +1 (види слика). Ако некое теме има уникатна вредност, тоа значи дека од него не излегува отсечка, па за него вредноста е 0.

Влез

Во првиот ред е даден бројот N (0 < N ≤ 100 000) - бројот на темиња на многуаголникот.
Во следниот ред се дадени броевите A_i (1 ≤ A_i < 1 000 000 000) по редослед, почнувајќи од некое теме, разделени со по едно празно место.

Забелешка. За 40% од поените ќе важи: N ≤ 5 000

Излез

Отпечатете N броеви разделени со по едно празно место: вредноста барана за секое теме, по редослед на темињата како што се дадени во влезот.

Ограничувања

Временско ограничување: 500 milliseconds
Мемориско ограничување: 16 megabytes

Примери

влез
6
1 1 2 1 2 3

излез
3 2 2 3 2 0

Објаснување за примерот: Примерот е претставен на сликата.