Трішки пригод нікому не завадить

Аксель завжди мріяла стати авантюристкою. Є $30$ унікальних навичок, якими може володіти кожен авантюрист. Вона увійшла в гільдію авантюристів і побачила, що там стоять $n$ авантюристів. Вона зрозуміла, що вони збирають команду для нападу на боса. Кожен авантюрист має свій опис, що вказує на ті спеціальні навички, якими він володіє:

• спочатку кожен авантюрист описаний числом $0$;

• якщо авантюрист $i$ володіє навичкою з номером $x$, то до його опису додається число $2^{x-1}$.

Член команди вважається непотрібним, якщо кожен інший член цієї команди володіє всіма навичками, якими володіє непотрібний член. Команда вважається поганою, якщо є принаймні один непотрібний член. Команда з одного члену завжди вважається поганою.

Вам надані описи цих $n$ авантюристів в порядку, в якому вони стоять у формі масиву $a$. Команда може бути сформована тільки з одного послідовного сегмента масиву.

Ваша єдина мета - знайти, скільки є способів утворити погану команду.

Вхідні дані

Перший рядок містить ціле число $n$ $(1\le n\le 10^3)$ — довжина масиву $a$.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ $(0\le a_i<2^{30})$ — опис кожного авантюриста в гільдії.

Вихідні дані

Виведіть одне ціле число — кількість поганих команд, які можна сформувати.

Приклади

Примітка

У цьому прикладі погані команди такі:

1. $[1]$

2. $[2]$

3. $[3]$

4. $[4]$

5. $[5]$

6. $[2,3]$ в цій команді авантюрист зі значенням $2$ вважається непотрібним (він володіє навичкою з номером $2$, тоді як авантюрист зі значенням $3$ володіє навичками з номерами $1$ та $2$)

7. $[4,5]$ в цій команді авантюрист зі значенням $4$ вважається непотрібним (він володіє навичкою з номером $3$, тоді як авантюрист зі значенням $5$ володіє навичками з номерами $1$ та $3$)

Оцінювання

1. ($5$ балів): $n\le 40$;

2. ($20$ балів): $n\le 100$;

3. ($33$ бали): $a_i\in \{0,1\}$;

4. ($42$ бали): немає додаткових обмежень.