Как Вы уже поняли, Вадим очень любит как решать, так и составлять судоку с необычными правилами. В этой задаче он расскажет Вам про ренбан-линии. Эта линия может проходить через любое количество клеток, а значения из этих клеток образуют набор целых последовательных неповторяющихся чисел в любом порядке. Например, линия, проходящая через 5 клеток cо значениями 4,7,5,3,6, образует ренбан, а линия, проходящая через 3 клетки с значениями 2,1,8, — не является ренбаном.

В этот раз Вадим составил строку из N чисел и хочет поместить на неё ренбан-линию так, чтобы она проходила через какие-либо последовательные клетки (другими словами, подотрезок). Помогите ему найти количество способов это сделать.

В первой строке дано целое число N — количество чисел в строке Вадима (1 ≤ N ≤ 10⁵).

Во второй строке даны N целых чисел a_i — числа строки в порядке записи (1 ≤ a_i ≤ 10⁵).

Выведите количество способов разместить на строке ренбан.

В данном выше примере ренбан-линия может проходить через клетки подотрезков [4], [4,2,3], [4,2,3,1], [2], [2,3], [2,3,1], [3], [3,1,2], [1], [1,2], [2].