1.2 Interesting Strings
(RankList for this Question)
Score: 60pts
Time Limit: 3.00 sec
Dheeraj likes attempting weekly challenges and (occasionally) reading. No wonder Dheeraj is especially interested in texts concerning his favourite pastime.

Dheeraj calls a string interesting if it starts with "weekly" and ends with "challenges". Finding all interesting substrings (by substring Dheeraj means a subsequence of consecutive characters in a string) in a given text makes our hero especially joyful. Recently he felt an enormous fit of energy while reading a certain text. So Dheeraj decided to count all the interesting substrings in this text and brag about it all day long. Help him in this difficult task. Two substrings are considered different if they appear at the different positions in the text.
For simplicity, let us assume that Dheeraj's text can be represented as a single string

0 < L <= 10^6

Input Format
Input contains 2 lines.
First line contains the length of the string = L
And the second line contains a single non-empty string consisting of the lowercase Latin alphabet letters. Length of this string will not be greater than 10^6 characters.

Output Format
Print exactly one number — the number of interesting substrings of the given string.

Example 1


In the first sample the string "weeklychallengesisweeklychallenges" contains interesting substring "weeklychallenges" twice, also the whole string "weeklychallengesisweeklychallenges" is interesting.

Log In to solve the Question