世上只有一种英雄主义，就是在认清生活真相之后依然热爱生活。

Every evening Vitalya sets n alarm clocks to wake up tomorrow. Every alarm clock rings during exactly one minute and is characterized by one integer ai — number of minute after midnight in which it rings. Every alarm clock begins ringing at the beginning of the minute and rings during whole minute.

Vitalya will definitely wake up if during some m consecutive minutes at least k alarm clocks will begin ringing. Pay attention that Vitalya considers only alarm clocks which begin ringing during given period of time. He doesn't consider alarm clocks which started ringing before given period of time and continues ringing during given period of time.

Vitalya is so tired that he wants to sleep all day long and not to wake up. Find out minimal number of alarm clocks Vitalya should turn off to sleep all next day. Now all alarm clocks are turned on.

Input

First line contains three integers n, m and k (1 ≤ k ≤ n ≤ 2·105, 1 ≤ m ≤ 106) — number of alarm clocks, and conditions of Vitalya's waking up.

Second line contains sequence of distinct integers a1, a2, ..., an (1 ≤ ai ≤ 106) in which aiequals minute on which i-th alarm clock will ring. Numbers are given in arbitrary order. Vitalya lives in a Berland in which day lasts for 106 minutes.

Output

Output minimal number of alarm clocks that Vitalya should turn off to sleep all next day long.

Examples

input

Copy

3 3 2 3 5 1

output

Copy

1

input

Copy

5 10 3 12 8 18 25 1

output

Copy

0

input

Copy

7 7 2 7 3 4 1 6 5 2

output

Copy

6

input

Copy

2 2 2 1 3

output

Copy

0

Note

In first example Vitalya should turn off first alarm clock which rings at minute 3.

In second example Vitalya shouldn't turn off any alarm clock because there are no interval of 10 consequence minutes in which 3 alarm clocks will ring.

In third example Vitalya should turn off any 6 alarm clocks.

#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cstring> #include <cstdlib> #include <cmath> #include <stack> #include <queue> #include <set> #include <map> #include <vector> #include <ctime> #include <cctype> #include <bitset> #include <utility> #include <sstream> #include <complex> #include <iomanip> #define inf 0x3f3f3f3f typedef long long ll; using namespace std; int n,m,k,jg,a[200010],b[200010]; int main() { cin>>n>>m>>k; for(int i=1; i<=n; i++) cin>>a[i]; sort(a+1,a+n+1); for(int i=1,j=1; i<=n; i++) { b[j]=a[i]; if(i<k||b[j]-b[j-k+1]>=m) j++; else jg++; } cout<<jg<<endl; return 0; }

Let's denote a function

You are given an array a consisting of n integers. You have to calculate the sum of d(ai, aj)over all pairs (i, j) such that 1 ≤ i ≤ j ≤ n.

Input

The first line contains one integer n (1 ≤ n ≤ 200000) — the number of elements in a.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — elements of the array.

Output

Print one integer — the sum of d(ai, aj) over all pairs (i, j) such that 1 ≤ i ≤ j ≤ n.

Examples

input

Copy

5 1 2 3 1 3

output

Copy

4

input

Copy

4 6 6 5 5

output

Copy

0

input

Copy

4 6 6 4 4

output

Copy

-8

Note

In the first example:

d(a1, a2) = 0;d(a1, a3) = 2;d(a1, a4) = 0;d(a1, a5) = 2;d(a2, a3) = 0;d(a2, a4) = 0;d(a2, a5) = 0;d(a3, a4) =  - 2;d(a3, a5) = 0;d(a4, a5) = 2. #include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cstring> #include <cstdlib> #include <cmath> #include <stack> #include <queue> #include <set> #include <map> #include<unordered_map> #include <vector> #include <ctime> #include <cctype> #include <bitset> #include <utility> #include <sstream> #include <complex> #include <iomanip> #define inf 0x3f3f3f3f typedef long long ll; using namespace std; long double sum, jg; int n; ll t; int main() { scanf("%d",&n); unordered_map<ll,ll> num; for(int i = 1; i <= n; i++) { scanf("%lld",&t); jg += (i - 1) * t - sum - num[t - 1] + num[t + 1]; num[t]++; sum += t; } printf("%.0Lf\n",jg); return 0; }

Valentin participates in a show called "Shockers". The rules are quite easy: jury selects one letter which Valentin doesn't know. He should make a small speech, but every time he pronounces a word that contains the selected letter, he receives an electric shock. He can make guesses which letter is selected, but for each incorrect guess he receives an electric shock too. The show ends when Valentin guesses the selected letter correctly.

Valentin can't keep in mind everything, so he could guess the selected letter much later than it can be uniquely determined and get excessive electric shocks. Excessive electric shocks are those which Valentin got after the moment the selected letter can be uniquely determined. You should find out the number of excessive electric shocks.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of actions Valentin did.

The next n lines contain descriptions of his actions, each line contains description of one action. Each action can be of one of three types:

Valentin pronounced some word and didn't get an electric shock. This action is described by the string ". w" (without quotes), in which "." is a dot (ASCII-code 46), and w is the word that Valentin said.Valentin pronounced some word and got an electric shock. This action is described by the string "! w" (without quotes), in which "!" is an exclamation mark (ASCII-code 33), and wis the word that Valentin said.Valentin made a guess about the selected letter. This action is described by the string "? s" (without quotes), in which "?" is a question mark (ASCII-code 63), and s is the guess — a lowercase English letter.

All words consist only of lowercase English letters. The total length of all words does not exceed 105.

It is guaranteed that last action is a guess about the selected letter. Also, it is guaranteed that Valentin didn't make correct guesses about the selected letter before the last action. Moreover, it's guaranteed that if Valentin got an electric shock after pronouncing some word, then it contains the selected letter; and also if Valentin didn't get an electric shock after pronouncing some word, then it does not contain the selected letter.

Output

Output a single integer — the number of electric shocks that Valentin could have avoided if he had told the selected letter just after it became uniquely determined.

Examples

input

Copy

5 ! abc . ad . b ! cd ? c

output

Copy

1

input

Copy

8 ! hello ! codeforces ? c . o ? d ? h . l ? e

output

Copy

2

input

Copy

7 ! ababahalamaha ? a ? b ? a ? b ? a ? h

output

Copy

0

Note

In the first test case after the first action it becomes clear that the selected letter is one of the following: a, b, c. After the second action we can note that the selected letter is not a. Valentin tells word "b" and doesn't get a shock. After that it is clear that the selected letter is c, but Valentin pronounces the word cd and gets an excessive electric shock.

In the second test case after the first two electric shocks we understand that the selected letter is e or o. Valentin tries some words consisting of these letters and after the second word it's clear that the selected letter is e, but Valentin makes 3 more actions before he makes a correct hypothesis.

In the third example the selected letter can be uniquely determined only when Valentin guesses it, so he didn't get excessive electric shocks.

#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cstring> #include <cstdlib> #include <cmath> #include <stack> #include <queue> #include <set> #include <map> #include <vector> #include <ctime> #include <cctype> #include <bitset> #include <utility> #include <sstream> #include <complex> #include <iomanip> #define inf 0x3f3f3f3f typedef long long ll; using namespace std; int n,vis[30],ct,flag,jg,cta; char S[100010],ch[3]; int main() { scanf("%d",&n); for(int i = 0; i < n; i ++) { scanf("%s%s",ch,S); int cd = strlen(S); if(ch[0] == '.') { for(int i = 0; i < cd; i ++) vis[S[i] - 'a'] = -1; } else if(ch[0] == '!') { if(flag) jg ++; else { cta ++; int mx = 0; for(int i = 0; i < 26; i ++) mx = max(mx,vis[i]); for(int i = 0; i < 26; i ++) { if(vis[i] == mx) { int j = 0; for(; j < cd; j ++) { if(S[j] == i + 'a') { vis[i] ++; break; } } if(j == cd) vis[i] = -1; } else vis[i] = -1; } } } else { vis[S[0] - 'a'] = -1; if(flag) jg ++; } ct = 0; for(int i = 0; i < 26; i ++) if(vis[i]>= cta) ct ++; if(ct == 1) flag = 1; } printf("%d\n",jg ? jg-1 : jg); return 0; }

unordered_map ： 优点： 因为内部实现了哈希表，因此其查找速度非常的快 缺点： 哈希表的建立比较耗费时间

适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map