## DQUERY - D-query

Đọc đề đẹp hơn ở:

https://codeforces.com/group/FLVn1Sc504/contest/274490/problem/O

https://codeforces.com/group/FLVn1Sc504/contest/274490/problem/O

English | Vietnamese |

Given a sequence of n numbers a_{1}, a_{2}, ..., a_{n} and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence a_{i}, a_{i+1}, ..., a_{j}.

### Input

- Line 1: n (1 ≤ n ≤ 30000).
- Line 2: n numbers a
_{1}, a_{2}, ..., a_{n}(1 ≤ a_{i}≤ 10^{6}). - Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
- In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).

### Output

- For each d-query (i, j), print the number of distinct elements in the subsequence a
_{i}, a_{i+1}, ..., a_{j}in a single line.

### Example

Input5 1 1 2 1 3 3 1 5 2 4 3 5Output3 2 3

Added by: | Jimmy |

Date: | 2008-10-26 |

Time limit: | 1s-1.5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |

Resource: | Minesweeper |