Given a sequence of positive integers and another positive integer p. The sequence is said to be a perfect sequence if M≤m×p where M and m are the maximum and minimum numbers in the sequence, respectively.

Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (≤10^5) is the number of integers in the sequence, and p (≤ 10^9 ) is the parameter. In the second line there are N positive integers, each is no greater than 10^9.

Output Specification:

For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

Sample Input:

10 8
2 3 20 4 5 1 6 7 8 9

Sample Output:

8

思路

• 能使选出的数个数最大的方案，一定是在该递增序列中选择连续的若干个数的方案
• 如果强行进行O(n^2)的二重循环遍历，那么根据题目的数据范围，肯定是会超时的。这里有两种方法解决这个问题：二分查找和 two pointers。
• 本人利用 upper_bound() 函数来二分寻找第一个大于 m * p 的数的位置，那么 M 的最大数的位置即为该位置 -1。

注意点

• nums[i] * p 可能达到 10^{18}，可以使用 long long 来定义数组。

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 100000;

int main() {
    int n;
    long long p, nums[maxn];
    scanf("%d %lld", &n, &p);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &nums[i]);
    }
    sort(nums, nums + n);
    int ans = 0;
    long long m = nums[0];
    for (int i = 0; i < n; i++) {
        int j = upper_bound(nums + i + 1, nums + n, nums[i] * p) - nums - 1;
        if (j - i + 1 > ans) {
            ans = j - i + 1;
        }
    }
    printf("%d", ans);
    return 0;
}