← 返回题目列表

Codeforces · 145/D

D. 幸运对

中文机器翻译题面 查看原题

Petya非常喜欢幸运数字。大家都知道,幸运数字是正整数,其小数记录中仅包含幸运数字4和7。例如,数字47、744、4是幸运数字,而5、17、467则不是幸运数字。

Petya 有一个包含 n 个整数的数组 a。数组中的数字从 1 开始编号。不幸的是,Petya 一直行为不端,所以他的父母不允许他玩有很多幸运数字的数组。保证数组a中幸运数字不超过1000个。

Petya 需要找到不相交线段 [l1;r1] 和 [l2;r2] 的对数(1 ≤ l1 ≤ r1 < l2 ≤ r2 ≤ n,所有四个数字都是整数),使得子数组 a[l1..r1] 和子数组 a[l2..r2] 中不存在同时出现的幸运数字。帮助 Petya 数一下这样的对的数量。

输入

第一行包含一个整数 n (2 ≤ n ≤ 105) — 数组 a 的大小。第二行包含 n 个空格分隔的整数 ai (1 ≤ ai ≤ 109) — 数组 a。保证数组a中幸运数字不超过1000个。

输出

在单行上打印唯一的数字——问题的答案。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。

示例

输入 #1

4
1 4 2 4

输出 #1

9

输入 #2

2
4 7

输出 #2

1

输入 #3

4
4 4 7 7

输出 #3

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] 并且满足条件。