这场cf，我败在了老奶奶身上。

就做出来一道题。还上分了。

A题，台灯。

十分钟就过了吧，470分。但是prime passed（预测试通过）。当时觉得完了，又是一场0题之路。

可是上分了。搞搞笑笑。

#include <iostream>using namespace std;int main() {int t, n, m;cin >> t;while (t--) {cin >> n >> m;cout << (n * m + 1) / 2 << '\n';}
}

B 老奶奶们，败在了不会用vector，string。清空数组，排序。都是自己手写的，耗费了大量的时间。

B. Maria Breaks the Self-isolation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Maria is the most active old lady in her house. She was tired of sitting at home. She decided to organize a ceremony against the coronavirus.

She has nn friends who are also grannies (Maria is not included in this number). The ii-th granny is ready to attend the ceremony, provided that at the time of her appearance in the courtyard there will be at least aiai other grannies there. Note that grannies can come into the courtyard at the same time. Formally, the granny ii agrees to come if the number of other grannies who came earlier or at the same time with her is greater than or equal to aiai.

Grannies gather in the courtyard like that.

• Initially, only Maria is in the courtyard (that is, the initial number of grannies in the courtyard is 11). All the remaining nn grannies are still sitting at home.
• On each step Maria selects a subset of grannies, none of whom have yet to enter the courtyard. She promises each of them that at the time of her appearance there will be at least aiai other grannies (including Maria) in the courtyard. Maria can call several grannies at once. In this case, the selected grannies will go out into the courtyard at the same moment of time.
• She cannot deceive grannies, that is, the situation when the ii-th granny in the moment of appearing in the courtyard, finds that now there are strictly less than aiai other grannies (except herself, but including Maria), is prohibited. Please note that if several grannies appeared in the yard at the same time, then each of them sees others at the time of appearance.

Your task is to find what maximum number of grannies (including herself) Maria can collect in the courtyard for the ceremony. After all, the more people in one place during quarantine, the more effective the ceremony!

Consider an example: if n=6n=6 and a=[1,5,4,5,1,9]a=[1,5,4,5,1,9], then:

• at the first step Maria can call grannies with numbers 11 and 55, each of them will see two grannies at the moment of going out into the yard (note that a1=1≤2a1=1≤2 and a5=1≤2a5=1≤2);
• at the second step, Maria can call grannies with numbers 22, 33 and 44, each of them will see five grannies at the moment of going out into the yard (note that a2=5≤5a2=5≤5, a3=4≤5a3=4≤5 and a4=5≤5a4=5≤5);
• the 66-th granny cannot be called into the yard  — therefore, the answer is 66 (Maria herself and another 55 grannies).

Input

The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases in the input. Then test cases follow.

The first line of a test case contains a single integer nn (1≤n≤1051≤n≤105) — the number of grannies (Maria is not included in this number).

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤2⋅1051≤ai≤2⋅105).

It is guaranteed that the sum of the values nn over all test cases of the input does not exceed 105105.

Output

For each test case, print a single integer kk (1≤k≤n+11≤k≤n+1) — the maximum possible number of grannies in the courtyard.

Example

input

Copy

4
5
1 1 2 2 1
6
2 3 4 5 6 7
6
1 5 4 5 1 9
5
1 2 3 5 6

output

Copy

6
1
6
4

Note

In the first test case in the example, on the first step Maria can call all the grannies. Then each of them will see five grannies when they come out. Therefore, Maria and five other grannies will be in the yard.

In the second test case in the example, no one can be in the yard, so Maria will remain there alone.

The third test case in the example is described in the details above.

In the fourth test case in the example, on the first step Maria can call grannies with numbers 11, 22 and 33. If on the second step Maria calls 44 or 55 (one of them), then when a granny appears in the yard, she will see only four grannies (but it is forbidden). It means that Maria can't call the 44-th granny or the 55-th granny separately (one of them). If she calls both: 44 and 55, then when they appear, they will see 4+1=54+1=5 grannies. Despite the fact that it is enough for the 44-th granny, the 55-th granny is not satisfied. So, Maria cannot call both the 44-th granny and the 55-th granny at the same time. That is, Maria and three grannies from the first step will be in the yard in total.

一句话总结，满足最多的老奶奶在疫情期间想聚会的愿望。（老奶奶希望的人数如果超出她就觉得很危险，就不去了）

要排序，更简单的方法是倒检查，满足最大的老奶奶的需求。满足了就不用期望小的，大家一起来

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;void solve() {int n;cin >> n;vector<int> arr(n);for (int &el : arr)cin >> el;sort(arr.begin(), arr.end());for (int i = n - 1; i >= 0; i--) {if (arr[i] <= i + 1) {cout << i + 2 << '\n';return;}}cout << 1 << '\n';
}int main() {int t;cin >> t;while (t--)solve();
}

从此之后我就会写个函数vector了！

这道题的本质是切入满足最小值的最大值。

 c题还挺简单的，当时看了一眼，没想到如此简单。

也是怪我没读懂题，当时还以为要用dp，就放弃了。是自信不够。

第四题，看看这个图。和爱上的人。我不好评价。chan，china？？nmlgb。

可是第一次涨分，善始善终。

#include <iostream>
#include <algorithm>
#include <vector>#define int long longusing namespace std;signed main() {int n, len;cin >> n >> len;vector<int> A(2 * n);for (int i = 0; i < n; i++) {cin >> A[i];A[n + i] = A[i];}n *= 2;vector<int> B = {0}, C = {0};for (int i = 0; i < n; i++) B.push_back(B.back() + A[i]);for (int i = 0; i < n; i++) C.push_back(C.back() + (A[i] * (A[i] + 1)) / 2);int ans = 0;for (int i = 0; i < n; i++) {if (B[i + 1] >= len) {int z = upper_bound(B.begin(), B.end(), B[i + 1] - len) - B.begin();int cnt = C[i + 1] - C[z];int days = B[i + 1] - B[z];int too = len - days;cnt += ((A[z - 1] * (A[z - 1] + 1)) / 2);cnt -= (((A[z - 1] - too) * (A[z - 1] - too + 1)) / 2);ans = max(ans, cnt);}}cout << ans;
}