Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P203PROH - Chuỗi nguyên tố

Minduk là một người rất yêu thích số nguyên tố. Anh ta định nghĩa rằng : “Một chuỗi số nguyên được gọi là chuỗi nguyên tố nếu như số lượng số nguyên tố trong đó lớn hơn hoặc bằng số lượng số còn lại”.

Ví dụ: (1,3,2,6) là một chuỗi nguyên tố và (4,9,2,6) thì không phải.

Bạn được cung cấp một chuỗi số nguyên a gồm n số. Hãy giúp Minduk đếm số cặp (l,r) ( 1 ≤ l ≤ r ≤ n ) sao cho chuỗi con (al , al+1 , ..... ar ) là một chuỗi nguyên tố.

Input:

  • Dòng đầu tiên là một số nguyên n (1 ≤ n ≤ 105).
  • Dòng tiếp theo gồm n số nguyên ai (1 ≤ ai ≤ 106).

Output:

  • Một dòng duy nhất chứa số lượng chuỗi nguyên tố.

Examples

Input

Output

3

1 3 4

3

4

1 3 5 7

9


Được gửi lên bởi:adm
Ngày:2020-08-29
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM64 CPP CPP14 JAVA PYTHON PYTHON3

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.