Codeforces Round 750 (Div. 2) |
---|
Finished |
Kuzya started going to school. He was given math homework in which he was given an array $$$a$$$ of length $$$n$$$ and an array of symbols $$$b$$$ of length $$$n$$$, consisting of symbols '*' and '/'.
Let's denote a path of calculations for a segment $$$[l; r]$$$ ($$$1 \le l \le r \le n$$$) in the following way:
For example, let $$$a=[7,$$$ $$$12,$$$ $$$3,$$$ $$$5,$$$ $$$4,$$$ $$$10,$$$ $$$9]$$$, $$$b=[/,$$$ $$$*,$$$ $$$/,$$$ $$$/,$$$ $$$/,$$$ $$$*,$$$ $$$*]$$$, $$$l=2$$$, $$$r=6$$$, then the path of calculations for that segment is $$$[12,$$$ $$$4,$$$ $$$0.8,$$$ $$$0.2,$$$ $$$2]$$$.
Let's call a segment $$$[l;r]$$$ simple if the path of calculations for it contains only integer numbers.
Kuzya needs to find the number of simple segments $$$[l;r]$$$ ($$$1 \le l \le r \le n$$$). Since he obviously has no time and no interest to do the calculations for each option, he asked you to write a program to get to find that number!
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).
The third line contains $$$n$$$ symbols without spaces between them — the array $$$b_1, b_2 \ldots b_n$$$ ($$$b_i=$$$ '/' or $$$b_i=$$$ '*' for every $$$1 \le i \le n$$$).
Print a single integer — the number of simple segments $$$[l;r]$$$.
3 1 2 3 */*
2
7 6 4 10 1 2 15 1 */*/*//
8
Name |
---|