import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
read_int = lambda: int(input())
read_ints = lambda: list(map(int, input().split()))
read_str = lambda: input().strip()
read_strs = lambda: read_str().split(' ')
MAX = 10 ** 6 + 1
def solve():
n = read_int()
a = read_ints()
res = MAX
a_sorted = sorted(a)
res = min(res, (a_sorted[0]+1) // 2 + (a_sorted[1]+1)//2)
for i in range(0, n-1):
b, c = a[i], a[i+1]
if b < c:
b, c = c, b
if b > 2*c:
res = min(res, (b+1) // 2)
else:
res = min(res, (b+c+2) // 3)
for i in range(0, n-2):
b, c = a[i], a[i+2]
cnt = 0
if b & 1 and c & 1:
cnt += 1
b -= 1
c -= 1
res = min(res, (b+1)//2 + (c+1)//2 + cnt)
print(res)
solve()
#include <bits/stdc++.h>
# define int long long
using namespace std;
const int cnst = 2e5+5;
// const int mod = 1e9+7;
// const int mod = 998244353;
bool mutipletestcase = false;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
void output(int a) {
if(a == 1) cout << "YES" << endl;
else if(a == 0) cout << "NO" << endl;
else if(a == -1) cout << "-1" << endl;
if(mutipletestcase) return;
else exit(0);
}
int num[cnst];
bool debugging = false;
int plusone(int x) {
int a = num[x];
int b = num[x+1];
if(b > a) swap(a, b);
int y = min(a-b, b);
b -= y;
if(b == 0) return a/2+a%2;
a -= y*2;
return y+((b+a+2)/3);
}
int plustwo(int x) {
int a = num[x];
int b = num[x+2];
int min1 = min(a, b);
int diff = abs(a-b);
return min1+(diff/2+diff%2);
}
void solve() {
int n; cin >> n;
priority_queue<int, vector<int>, greater<int>> pq;
for(int i = 1; i<=n; i++) {
cin >> num[i];
pq.push(num[i]);
}
int ans = 0;
ans += pq.top()/2+pq.top()%2; pq.pop();
ans += pq.top()/2+pq.top()%2; pq.pop();
for(int i = 1; i<=n-2; i++) {
ans = min(ans, plustwo(i));
}
for(int i = 1; i<n; i++) {
ans = min(ans, plusone(i));
// cerr << num[i] << " " << num[i+1] << " " << plusone(i) << endl;
}
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(false);
int t = 1;
if(mutipletestcase || debugging) cin >> t;
while(t--) solve();
}32. Longest Valid Parentheses | Cutting a material |
Bubble Sort | Number of triangles |
AND path in a binary tree | Factorial equations |
Removal of vertices | Happy segments |
Cyclic shifts | Zoos |
Build a graph | Almost correct bracket sequence |
Count of integers | Differences of the permutations |
Doctor's Secret | Back to School |
I am Easy | Teddy and Tweety |
Partitioning binary strings | Special sets |
Smallest chosen word | Going to office |
Color the boxes | Missing numbers |
Maximum sum | 13 Reasons Why |
Friend's Relationship | Health of a person |
Divisibility | A. Movement |