D. Счастливая пара
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.

У Пети есть массив a из n целых чисел. Числа в массиве нумеруются начиная с 1. К сожалению, в последнее время Петя плохо писал контесты, поэтому родители не разрешают ему играть с массивами, в которых много счастливых чисел. Гарантируется, что в массиве a не более 1000 элементов являются счастливыми.

Пете нужно найти количество пар непересекающихся отрезков [l1;r1] и [l2;r2] (1 ≤ l1 ≤ r1 < l2 ≤ r2 ≤ n, все четыре числа — целые) таких, что нет такого счастливого числа, которое встречается одновременно и в подмассиве a[l1..r1], и в подмассиве a[l2..r2]. Помогите Пете посчитать количество таких пар.

Входные данные

В первой строке задано целое число n (2 ≤ n ≤ 105) — размер массива a. Во второй строке задано через пробел n целых чисел ai (1 ≤ ai ≤ 109) — массив a. Гарантируется, что в массиве a не более 1000 элементов являются счастливыми.

Выходные данные

В единственной строке выведите одно число — ответ на задачу.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
4
1 4 2 4
Выходные данные
9
Входные данные
2
4 7
Выходные данные
1
Входные данные
4
4 4 7 7
Выходные данные
9
Примечание

Подмассив a[l..r] — массив из элементов al, al + 1, ..., ar.

В первом примере есть 9 возможных пар, которые удовлетворяют условие: [1, 1] и [2, 2], [1, 1] и [2, 3], [1, 1] и [2, 4], [1, 1] и [3, 3], [1, 1] и [3, 4], [1, 1] и [4, 4], [1, 2] и [3, 3], [2, 2] и [3, 3], [3, 3] и [4, 4].

Во втором примере есть только одна возможная пара отрезков — [1;1] и [2;2] и она удовлетворяет условие.