Algorithm

D. Pair of Numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/359/problem/D
input
standard input
output
standard output

Simon has an array a1, a2, ..., an, consisting of n positive integers. Today Simon asked you to find a pair of integers l, r (1 ≤ l ≤ r ≤ n), such that the following conditions hold:

  1. there is integer j (l ≤ j ≤ r), such that all integers al, al + 1, ..., ar are divisible by aj;
  2. value r - l takes the maximum value among all pairs for which condition 1 is true;

Help Simon, find the required pair of numbers (l, r). If there are multiple required pairs find all of them.

Input

The first line contains integer n (1 ≤ n ≤ 3·105).

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 106).

Output

Print two integers in the first line — the number of required pairs and the maximum value of r - l. On the following line print all l values from optimal pairs in increasing order.

Examples
input
Copy
5
4 6 9 3 6
output
Copy
1 3
2
input
Copy
5
1 3 5 7 9
output
Copy
1 4
1
input
Copy
5
2 3 5 7 11
output
Copy
5 0
1 2 3 4 5
Note

In the first sample the pair of numbers is right, as numbers 6, 9, 3 are divisible by 3.

In the second sample all numbers are divisible by number 1.

In the third sample all numbers are prime, so conditions 1 and 2 are true only for pairs of numbers (1, 1), (2, 2), (3, 3), (4, 4), (5, 5).



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int const N = 3e5 + 1;
int n, a[N], r_minus_l;
pair<int, int> sparse[N][19];
vector<int> starts, starts_tmp;

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int calc_log(int len) {
	int log = 0;
	while((1 << log) <= len)
		++log;
	return --log;
}

int min_query(int l, int r) {
	int log = calc_log(r - l + 1);
	return min(a[sparse[l][log].first], a[sparse[r + 1 - (1 << log)][log].first]);
}

int gcd_query(int l, int r) {
	int log = calc_log(r - l + 1);
	return gcd(sparse[l][log].second, sparse[r + 1 - (1 << log)][log].second);
}

void can(int mid) {
	starts_tmp.clear();
	for(int i = 0; i <= n - mid; ++i)
		if(min_query(i, i + mid - 1) == gcd_query(i, i + mid - 1))
			starts_tmp.push_back(i + 1);
}

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		scanf("%d", a + i);

	for(int i = 0; i < n; ++i) {
		sparse[i][0].first = i;
		sparse[i][0].second = a[i];
	}

	for(int j = 1; (1 << j) <= n; ++j)
		for(int i = 0; i + (1 << j) - 1 < n; ++i) {
			if(a[sparse[i][j - 1].first] < a[sparse[i + (1 << (j - 1))][j - 1].first])
				sparse[i][j].first = sparse[i][j - 1].first;
			else
				sparse[i][j].first = sparse[i + (1 << (j - 1))][j - 1].first;

			sparse[i][j].second = gcd(sparse[i][j - 1].second, sparse[i + (1 << (j - 1))][j - 1].second);
		}

	int l = 1, r = n, mid;
	while(l <= r) {
		mid = (l + r) / 2;
		can(mid);
		if(!starts_tmp.empty()) {
			l = mid + 1;
			r_minus_l = mid;
			starts.swap(starts_tmp);
		} else
			r = mid - 1;
	}

	printf("%d %d\n", (int)starts.size(), r_minus_l - 1);
	for(int i = 0; i < (int)starts.size(); ++i)
		printf("%d ", starts[i]);
	puts("">;

    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5
4 6 9 3 6

Output

x
–
+
cmd
1 3
2
Advertisements

Demonstration

Codeforces Solution-Pair of Numbers-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+