Searching and Sorting are very important areas in computer science. Efficient sorting algorithms are required for optimizing the use of other algorithms that require sorted lists to work correctly, for example to do binary search sorting is required.We present two problems here based on variant of binary search and sorting. Hope you will appreciate them.

Problem 1:

You are given some set of numbers. By choosing three numbers we may be able to construct a triangle. In this problem we ask you to find out the number of invalid triangles formed from these set of numbers. The degenerate traiangles are considered to be valid traiangles.

Input Specification

Input contains N(<= 1000), followed by N numbers in the next line.The numbers are separated by spaces and each number is > 0 and < 106.

Output Specification

Print the number of invalid traingles that can be formed.

Sample Input and Output

Input: 5 1 2 3 4 10 Output: 7

Problem 2:

Given a String and a character set we need to find out the length of the smallest substring which contains all the characters of the set.

Input Specification

The input contains a string(length<=105) made up of small letters from english language followed by number of characters N(< 26) and then N chracters in the next line follow separated by spaces.

Output Specification

The output must contain the length of the smallest substring which contains all the characters from the character set. If no such substring exists report -1.

Sample Input and Output

Input: applelooksred 3 e a p
Output: 5