# HackerEarth A special sequence problem solution

In this HackerEarth A special sequence problem solution An array A contains integers with the following constraints:
1. A contains elements in sorted order.
2. Integer i occurs i x floor(sqrt(i)) + ceil(i/2) times in the array.
3. All elements are greater than or equal to 1.
You are given Q queries of type:

L R: Find the number of distinct values present in subarray A[L...R].

## HackerEarth A special sequence problem solution.

`#include<bits/stdc++.h>#define ll long doubleusing namespace std;vector<long long>p;signed main(){    long long sum = 0;    p.push_back(0);    for(ll i = 1 ; i <= 500000 ; i++){        long long val = i*floor(sqrt(i)) + ceil(i/2);        p.push_back(val);    }    int sz = p.size();    for(int i = 1 ; i < sz ; i++){        p[i] += p[i-1];    }    int q;    cin >> q;    assert(1 <= q and q <= 100000);    while(q--){        long long l, r;        cin >> l >> r;        assert(1 <= l and l <= r and r <= 10000000000000);        int s = 0;        int e = sz - 1;        int ans1 = -1;        while(s <= e){            int m = (s + e)/2;            if(p[m] < l){                ans1 = m;                s = m + 1;            }            else{                e = m - 1;            }        }        ans1++;        s = 0;        e = sz - 1;        int ans2 = -1;        while(s <= e){            int m = (s + e)/2;            if(p[m] < r){                ans2 = m;                s = m + 1;            }            else{                e = m - 1;            }        }        ans2++;        cout << (ans2 - ans1 + 1) << endl;    }   }`

### Second solution

`from bisect import bisect_leftfrom math import sqrtimport osimport sysfrom io import BytesIO, IOBase_str = strstr = lambda x=b"": x if type(x) is bytes else _str(x).encode()BUFSIZE = 8192class FastIO(IOBase):    newlines = 0    def __init__(self, file):        self._fd = file.fileno()        self.buffer = BytesIO()        self.writable = "x" in file.mode or "r" not in file.mode        self.write = self.buffer.write if self.writable else None    def read(self):        while True:            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))            if not b:                break            ptr = self.buffer.tell()            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)        self.newlines = 0        return self.buffer.read()    def readline(self):        while self.newlines == 0:            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))            self.newlines = b.count(b"\n") + (not b)            ptr = self.buffer.tell()            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)        self.newlines -= 1        return self.buffer.readline()    def flush(self):        if self.writable:            os.write(self._fd, self.buffer.getvalue())            self.buffer.truncate(0), self.buffer.seek(0)class IOWrapper(IOBase):    def __init__(self, file):        self.buffer = FastIO(file)        self.flush = self.buffer.flush        self.writable = self.buffer.writable        self.write = lambda s: self.buffer.write(s.encode("ascii"))        self.read = lambda: self.buffer.read().decode("ascii")        self.readline = lambda: self.buffer.readline().decode("ascii")input = lambda: sys.stdin.readline().rstrip("\r\n")a = [2]while a[-1] < 1e13:    i = len(a) + 1    a += [a[-1] + i * int(sqrt(i)) + (i + 1) // 2]q = int(input())while q > 0:    q -= 1    l, r = map(int, input().split())    print(bisect_left(a, r) - bisect_left(a, l) + 1)`