SEQ5 - How many subsequences

Tom has again maths, and the teacher writes countless tables with exercises.... so boring. Then he remembers an old problem of informatics that he thought in a dream. He remembered, he has a number of positive integers and the job was to know how many subsequences that have between L and U distinct elements exist in that range. So the boring hour will pass quicker. But he needs your help, he is too exhausted after two hours of math with the agitated teacher.

Input

The first line of input file contains positive N, L, U. following N lines will contain a positive integer, each representing an element of the series.

Output

The first line of the output will display the number of sequences containing between L and U distinct elements.

Example

Input:
4 1 2
231
19
7
19

Output:
8

Notes:

  • 1 <= L <= U <= N <= 2^20
  • The value of an item number is a positive integers [1, 2^32-1].
  • A subsequence is a lot of items that appear on consecutive positions in the initial row.
  • Be careful with certain languages. Large input data.
  • Tom thanks you for solving this problem and he awards you with points.


Added by:Pripoae Toni
Date:2008-09-29
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:Mircea Pasoi

hide comments
2012-10-02 04:52:21 Mark Gordon
There also seems to be unexpected whitespace in the data
2011-10-30 19:43:51 Aamir Khan
Explanation of test cases please. For 1 element sequences {231},{19},{7},{19} all are valid ?

From msg555: The author is looking for consecutive subsequences that have between L and U distinct elements. For the example they are (231), (231, 19), (19), (19, 7), (19, 7, 19), (7), (7, 19), (19)

Last edit: 2012-10-02 04:54:08
2011-10-01 13:52:42 :D
Please remember that the problem requires heavy optimization. You pretty much will need fast input reading and efficient O(N) algo.
2010-05-31 06:26:58 :D
There are 0 values in the sequence.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.