import java.io.*;
import java.util.*;
@SuppressWarnings("unchecked") public class zoltan {
static final int MAXN = 200010; static final long MOD = 1000000007;
static int N; static int[] A = new int[MAXN];
static TreeSet<Integer> X = new TreeSet<Integer>();
static ArrayList<Integer> cX = new ArrayList<Integer>();
static int[] tree1 = new int[4 * MAXN]; static int[] tree2 = new int[4 * MAXN];
static int[] lis = new int[MAXN]; static int[] lds = new int[MAXN];
static ArrayList<Integer> best = new ArrayList<Integer>();
static int[] id1 = new int[MAXN]; static int[] id2 = new int[MAXN];
static long[] DP1 = new long[MAXN]; static long[] DP2 = new long[MAXN];
static ArrayList<Integer>[] nodes1 = new ArrayList[MAXN];
static ArrayList<Integer>[] nodes2 = new ArrayList[MAXN];
static int[] next1 = new int[MAXN]; static int[] next2 = new int[MAXN];
static ArrayList<long[]> sum1 = new ArrayList<long[]>();
static ArrayList<long[]> sum2 = new ArrayList<long[]>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken()); X.add(A[i]);
}
for (int i : X) cX.add(i); for (int i = 0; i < N; i++) A[i] = compress(A[i]);
int max = 0; int maxLIS = 0; int maxLDS = 0;
for (int i = N - 1; i >= 0; i--) {
lis[i] = queryMax(tree1, 1, 1, N, A[i] + 1, N) + 1; updateMax(tree1, 1, 1, N, A[i], lis[i]);
lds[i] = queryMax(tree2, 1, 1, N, 1, A[i] - 1) + 1; updateMax(tree2, 1, 1, N, A[i], lds[i]);
maxLIS = Math.max(maxLIS, lis[i]); maxLDS = Math.max(maxLDS, lds[i]);
max = Math.max(max, lis[i] + lds[i] - 1);
}
for (int i = 0; i < N; i++) if (lis[i] + lds[i] - 1 == max) best.add(i);
for (int i = 0; i <= maxLIS; i++) nodes1[i] = new ArrayList<Integer>();
for (int i = N - 1; i >= 0; i--) { id1[i] = nodes1[lis[i]].size(); nodes1[lis[i]].add(A[i]); }
for (int i = 0; i <= maxLIS; i++) sum1.add(new long[4 * nodes1[i].size()]);
for (int i = N - 1; i >= 0; i--) {
if (lis[i] == 1) { DP1[i] = 1; updateSum(sum1.get(lis[i]), 1, 0, nodes1[lis[i]].size() - 1, id1[i], 1); continue; }
while (next1[lis[i]] < nodes1[lis[i] - 1].size() && A[i] > nodes1[lis[i] - 1].get(next1[lis[i]])) {
next1[lis[i]]++;
}
long cur = querySum(sum1.get(lis[i] - 1), 1, 0, nodes1[lis[i] - 1].size() - 1, next1[lis[i]], nodes1[lis[i] - 1].size() - 1);
DP1[i] = cur % MOD; updateSum(sum1.get(lis[i]), 1, 0, nodes1[lis[i]].size() - 1, id1[i], DP1[i]);
}
for (int i = 0; i <= maxLDS; i++) nodes2[i] = new ArrayList<Integer>();
for (int i = N - 1; i >= 0; i--) { id2[i] = nodes2[lds[i]].size(); nodes2[lds[i]].add(A[i]); }
for (int i = 0; i <= maxLDS; i++) sum2.add(new long[4 * nodes2[i].size()]);
for (int i = N - 1; i >= 0; i--) {
if (lds[i] == 1) { DP2[i] = 1; updateSum(sum2.get(lds[i]), 1, 0, nodes2[lds[i]].size() - 1, id2[i], 1); continue; }
while (next2[lds[i]] < nodes2[lds[i] - 1].size() && A[i] < nodes2[lds[i] - 1].get(next2[lds[i]])) {
next2[lds[i]]++;
}
long cur = querySum(sum2.get(lds[i] - 1), 1, 0, nodes2[lds[i] - 1].size() - 1, next2[lds[i]], nodes2[lds[i] - 1].size() - 1);
DP2[i] = cur % MOD; updateSum(sum2.get(lds[i]), 1, 0, nodes2[lds[i]].size() - 1, id2[i], DP2[i]);
}
long ans = 0; for (int i : best) { ans += DP1[i] * DP2[i]; ans %= MOD; }
ans *= exp(2, N - max); ans %= MOD; System.out.println(max + " " + ans);
}
static void updateMax(int[] tree, int x, int l, int r, int pos, int val) { int mid = (l + r) / 2;
if (pos < l || pos > r) return ; if (l == r) { tree[x] = val; return ; }
updateMax(tree, 2 * x, l, mid, pos, val); updateMax(tree, 2 * x + 1, mid + 1, r, pos, val);
tree[x] = Math.max(tree[2 * x], tree[2 * x + 1]);
}
static int queryMax(int[] tree, int x, int l, int r, int tl, int tr) { int mid = (l + r) / 2;
if (r < tl || l > tr) return 0; if (tl <= l && r <= tr) return tree[x];
return Math.max(queryMax(tree, 2 * x, l, mid, tl, tr), queryMax(tree, 2 * x + 1, mid + 1, r, tl, tr));
}
static void updateSum(long[] tree, int x, int l, int r, int pos, long val) { int mid = (l + r) / 2;
if (pos < l || pos > r) return ; if (l == r) { tree[x] = val; return ; }
updateSum(tree, 2 * x, l, mid, pos, val); updateSum(tree, 2 * x + 1, mid + 1, r, pos, val);
tree[x] = tree[2 * x] + tree[2 * x + 1];
}
static long querySum(long[] tree, int x, int l, int r, int tl, int tr) { int mid = (l + r) / 2;
if (r < tl || l > tr) return 0; if (tl <= l && r <= tr) return tree[x];
return querySum(tree, 2 * x, l, mid, tl, tr) + querySum(tree, 2 * x + 1, mid + 1, r, tl, tr);
}
static int compress(int val) {
int low = 0; int high = cX.size() - 1; int res = 0;
while (low <= high) { int mid = (low + high) / 2;
if (cX.get(mid) >= val) { res = mid; high = mid - 1; } else low = mid + 1;
}
return res + 1;
}
static long exp(long base, int pow) {
if (pow == 0) return 1; if (pow == 1) return (base + MOD) % MOD;
long res = exp(base, pow / 2); res = (res * res + MOD) % MOD;
if (pow % 2 == 1) res = (res * base + MOD) % MOD;
return (res + MOD) % MOD;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
154 ms |
27264 KB |
Output is correct |
| 2 |
Correct |
153 ms |
27116 KB |
Output is correct |
| 3 |
Correct |
153 ms |
27180 KB |
Output is correct |
| 4 |
Correct |
148 ms |
27112 KB |
Output is correct |
| 5 |
Correct |
153 ms |
27200 KB |
Output is correct |
| 6 |
Correct |
149 ms |
27112 KB |
Output is correct |
| 7 |
Correct |
222 ms |
27496 KB |
Output is correct |
| 8 |
Correct |
221 ms |
27496 KB |
Output is correct |
| 9 |
Correct |
231 ms |
27340 KB |
Output is correct |
| 10 |
Correct |
224 ms |
27344 KB |
Output is correct |
| 11 |
Runtime error |
817 ms |
65536 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
768 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
835 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
916 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
904 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
976 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
851 ms |
65536 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
847 ms |
65536 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
807 ms |
65536 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
846 ms |
65536 KB |
Execution killed with signal 9 |
