字符数对

给定一个由字符 o 和 x 组成的长度为 N 的字符串 S。请计算满足以下所有条件的整数对（l，r）的数量：

（1）1≤l≤r≤N；

（2）在字符串 S 的子串 S[l...r]（从第 l 个字符到第 r 个字符）中，同时包含 o 和 x 两种字符。

时间限制：1000ms，内存限制：256MB

输入格式

第一行，一个整数 N；

第二行，一个字符串 S。

输出格式

输出满足条件的整数对的数量。

输入样例#1

4
oxxo

输出样例#1

5

输入样例#2

7
xoxooxx

输出样例#2

19

数据范围：

1≤N≤106；S 仅由字符 o 和 x 组成。

咖啡机

一台自动咖啡机按以下规则接单：制作一杯咖啡需要 c 秒，只有当前订单制作完成后，才能处理下一个订单。如果在制作期间，接到新订单，则做忽略处理。

有 n 位顾客下单，其中第 i 位顾客的下单时间为第 ti 秒，保证所有下单时间均不重复。这台咖啡机最多能完成多少杯订单？

时间限制：1000ms，内存限制：256MB

输入格式

第一行，两个整数表示 n、c；

第二行，n 个整数表示 t1、t2、t3、……、tn。

输出格式

这台咖啡机最多能完成多少杯订单。

输入样例#1

6 5
1 3 12 10 8 7

输出样例#1

3

输入样例#2

3 2
0 2 4

输出样例#2

3

输入样例#3

10 3
0 3 4 9 15 12 6 17 19 20

输出样例#3

7

数据范围：

1≤n≤100；1≤c≤1000；0≤ti≤1000。

无法整除的数

给定一个长度为 N 的数列 A。请计算满足以下条件的下标 i（1≤i≤N）的数量：

对于任意 j（1≤j≤N且 i≠j），元素 Ai 不能被 Aj 整除。

时间限制：1000ms，内存限制：256MB

输入格式

第一行，一个整数 N；

第二行，N 个整数表示 A1、A2、……、AN。

输出格式

输出一个整数，表示满足条件的下标数量。

输入样例#1

5
2 3 9 11 19

输出样例#1

4

输入样例#2

10
11 18 45 28 8 19 89 86 2 4

输出样例#2

5

数据范围：

所有输入均为整数；1≤N≤2×105；1≤Ai≤106。

替换

有一个包含 N 个正整数 A1、A2、……、AN 的数列 A。接下来将进行 Q 次操作：

在第 i 次操作中，将数列中所有值为 Bi 的元素替换为 Ci。请针对每次操作（1≤i≤Q），输出操作后数列 A 的所有元素之和 Si。

时间限制：1000ms，内存限制：256MB

输入格式

第一行，一个整数 N；

第二行，N 个整数 A1、A2、……、AN；

第三行，一个整数 Q。

接下来 Q行，每行两个整数 Bi、Ci。

输出格式

输出 Q行，每行一个整数 Si，表示每次操作后的数列总和。注意：Si 可能超出32 位整数范围。

输入样例#1

4
1 2 3 4
3
1 2
2 4
3 4

输出样例#1

11
15
16

输入样例#2

5
1 2 3 4 5
5
1 2
2 3
3 4
4 5
5 1

输出样例#2

16
18
21
25
5

数据范围：

1≤N、Q、Ai、Bi、Ci≤105，Bi≠Ci。