Пусть есть помеченное дерево, то есть вершины дерева пронумерованы от 1 до n.

Определим вес дерева так: сумма по всем ребрам (uv) величин u · sz_uv(u) + v · sz_vu(v). Здесь sz_vu(v) — это размер того поддерева, в котором окажется v после удаления ребра (vu).

Дан массив a размера n. Элементы массива либо являются целыми числами от 1 до n−1, либо равны −1. v-й элемент соответствует степени вершины v. Назовём дерево размера n хорошим, если для всех v таких, что a_v ≠ −1, верно, что степень вершины v равна a_v. Другими словами, если a_v = −1, то степень вершины v может быть любой, а иначе степень фиксирована и равна a_v.

Выберем одно хорошее дерево случайно и равновероятно. Пусть E — матожидание веса этого дерева. Найдите целую часть E.

В первой строке записано одно число n — размер дерева (2 ≤ n ≤ 10⁶).

Во второй строке записан массив длины n, все элементы которого являются либо числами от 1 до n−1 (степень фиксирована), либо равны −1 (степень может быть любой). Сумма модулей элементов массива не превосходит 2n−2.

Выведите целую часть E.